1103. 게임

문제 링크

1103. 게임

문제 코드

num_list = list(map(int,input().split()))

row = num_list[0]
col = num_list[1]

maze = [[0 for i in range(col)]for j in range(row)]
visited = [[0 for i in range(col)]for j in range(row)]
cycle = [[0 for i in range(col)]for j in range(row)]

for i in range(row):
    tmp = input()
    for j in range(col):
        maze[i][j] = tmp[j]

max_count = 0

def back_tracking(x,y,count):

    global row
    global col
    global max_count

    if max_count == float('INF'):
        return

    visited[x][y] = count
    max_count = max(max_count,count)

    move_len = int(maze[x][y])

    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    for i in range(4):
        next_x = x+(dx[i]*move_len)
        next_y = y+(dy[i]*move_len)
        if 0<=next_x<row and 0<= next_y <col and maze[next_x][next_y] !='H':

            if cycle[next_x][next_y] == 1:
                max_count = float('INF')
                return
            elif visited[next_x][next_y] == 0 or visited[next_x][next_y] < count+1:
                cycle[next_x][next_y] = 1
                back_tracking(next_x,next_y,count+1)
                cycle[next_x][next_y] = 0
        else :
            if count > max_count:
                max_count = count


visited[0][0] = 1
back_tracking(0,0,1)

if max_count != float('INF'):
    print(max_count)
else:
    print(-1)

문제 풀이

• 기존의 그래프 문제와 다르게, visited와 cycle 두개의 확인 지표가 필요하다.
• 처음에는 기존의 maze 문제처럼 BFS로 풀려고했다.
• 왔던 타일을 다시 오는 경우가 발생할 수 있기 때문에 BFS로 풀 수 없다는 것을 알게되었다.
• DFS로 변경했더니, visited를 설정해 줄 수 없어서 recursion 횟수가 급증했다.
• visited 배열을 DP로 활용하고, 무한번 왔다갔다 하는것을 체크하기 위한 cycle 배열을 추가했다.
• visited에는 기본적으로 지금까지의 count가 들어간다.
• 프루닝을 할때 다음 구슬의 위치가 현재 count+1보다 크면 이미 더 좋은 방법으로 거길 지나간 것으로 판단해서 프루닝을 해준다.
• 추가적인 프루닝으로 맥스 카운트가 이미 inf이면 그 후의 계산이 의미없으므로 바로 return하도록 했다.
• 1등 코드도 거의 유사함