always_here

지식을 공유하고 함께 성장하는 엔지니어 as_always 입니다

AS_ALWAYS

알고리즘

구름톤 챌린지 Day09 - Day10 [완전탐색]

nauung_always 2023. 9. 4. 09:10
728x90

[ 문제 9 ]

N, K = map(int, input().split())

matrix = []
for i in range(N):
    matrix.append(list(input().split()))
result = [[0] * N for i in range(N)]

dx = [0, -1, 1, 0, 0]
dy = [0, 0, 0, 1, -1]
for k in range(K):
    xx, yy = map(int, input().split())
    xx -= 1
    yy -= 1
    for i in range(5):
        if 0 <= xx + dx[i] < N and 0 <= yy + dy[i] < N:
            if matrix[xx+dx[i]][yy+dy[i]] == '0':
                result[xx+dx[i]][yy+dy[i]] = int(result[xx+dx[i]][yy+dy[i]]) + 1
            elif matrix[xx+dx[i]][yy+dy[i]] == '@':
                result[xx+dx[i]][yy+dy[i]] = int(result[xx+dx[i]][yy+dy[i]]) + 2
            else:
                continue
                
print(max([max(i) for i in result]))               
# print(max(map(max,result)))

문제 7과 비슷하게 상하좌우를 돌면서 값을 확인한다. 이때, 현재 위치도 고려해야하기 때문에 dx = 0, dy = 0 을 추가로 고려해주었다. score 계산을 위한 result 행렬을 추가로 지정했고 모두 0으로 채워져있는 행렬로 구현했다.

마지막에 전체 행렬에서의 최댓값을 구해야하는데, 이차원 리스트이기 때문에 그냥 max함수를 사용할 수 없었고 result 행렬 안의 각 리스트 마다의 max값을 구해서 리스트로 만들고 만든 일차원 리스트에서 max값을 뽑는 방식을 사용했다. 
이때, map 함수를 사용할 수 도 있다. ! 

[ 문제 10 ]

N = int(input())
Rg, Cg = map(int, input().split())
Rp, Cp = map(int, input().split())
Rg, Cg = Rg - 1, Cg - 1
Rp, Cp = Rp - 1, Cp - 1

matrix = []
for i in range(N):
    matrix.append(list(input().split()))

direction_dic = {"U": [-1, 0], "D": [1, 0], "L": [0, -1], "R": [0, 1]}

scores = []

dx = [Rg, Rp]
dy = [Cg, Cp]

for i in range(2):
    move = 0
    score = 0
    x, y = dx[i], dy[i]
    count = [[0] * N for _ in range(N)]
    visited = [[0] * N for _ in range(N)]
    while visited[x][y] != 1:
        visited[x][y] = 1
        if move == 0:
            move = int(matrix[x][y][:-1])
            direction = matrix[x][y][-1]
        move -= 1
        x = (x + direction_dic[direction][0]) % N
        y = (y + direction_dic[direction][1]) % N
        score += 1
    scores.append(score)
        
if scores[0] > scores[1]:
    print(f'goorm {scores[0]}')
else: 
    print(f'player {scores[1]}')
  1. 위 문제에서 x, y 값이 범위를 벗어난 경우 반대쪽 끝 값으로 위치를 이동하게 된다.
    [나머지 연산을 통해 해결]
    -> 10 % 10 = 0 우측 끝에 도달하여 왼쪽 끝으로 돌아간 경우
    -> -1 % 10 = 0 왼쪽 끝이 -1인 경우에 10으로 나눈 나머지는 9가 나온다 오른쪽 끝으로 간 경우
    -> (x + dx[0]) % N 으로 작성하면 해결된다. 
  2. 문자열로 지정된 정보에서 마지막 값이 방향이 되고 그 전까지의 값이 이동 수가 된다.
    matrix[i][j][1] == 'L'
    -> 위의 식으로 진행하려고 했으나 만약 count가 일의자리가 아닌 10, 100 으로 증가한다면, matrix[i][j][1]이 command의 값을 가지지 못한다. 
    -> direction : matrix{:-1], count : matrix[-1] 로 작성하면 해결된다. 
  3.  <-주의->
    이 문제에서 위쪽은 행 번호가 감소하는 방향이다 !
728x90