[BOJ] Q1103 게임

[BOJ] Q1103 게임

Question

Language: Python

Difficulty: Gold 2

해당 문제는 동전을 이동시켜서 구멍에 넣거나 격자외부로 이동하기까지의 최대 이동값을 구하는 문제이다. 각각의 방향에 대해서 dfs 방식으로 순회를 하면서 dp를 통해 최대값을 비교하면서 순회한다.

이런 유형의 문제는 bfs, dfs를 고려할 수 있지만, visited을 개별적으로 관리해야되는 경우 dfs를 활용해야한다.

하지만 특정 입력에 대해서는 무한히 반복하는 경우도 발생하기 때문에, 싸이클을 판별하는 것이 중요하다. visited 배열을 둬서 특정 위치에 대한 이동 횟수가 갱신될때, 이미 해당 위치를 이전에 방문하는 경우 사이클이 발생할 가능성이 있기 때문에 visited 한 경우 사이클이 있음을 뜻하면 바로 -1를 출력하고 종료를 할 수 있도록 한다.

if 0<=next_row <n_rows and 0<=next_col<n_cols and board[next_row][next_col]!="H" and dp[next_row][next_col]<(count+1):
    # 다음 위치에 저장되어 있는 값보다 큰데, 해당 위치를 이전에 방문했다는 것은 사이클이 발생했다는 뜻이다.
    if visited[next_row][next_col]:
        print(-1)
        exit()

Solution

import sys
from collections import deque
def dfs(row,col,count):
    global max_count,visited
    max_count=max(max_count,count)
    
    number=int(board[row][col])
    for dir in range(4):
        next_row=row+dy[dir]*number
        next_col=col+dx[dir]*number

        if 0<=next_row <n_rows and 0<=next_col<n_cols and board[next_row][next_col]!="H" and dp[next_row][next_col]<(count+1):
            # 다음 위치에 저장되어 있는 값보다 큰데, 해당 위치를 이전에 방문했다는 것은 사이클이 발생했다는 뜻이다.
            if visited[next_row][next_col]:
                print(-1)
                exit()
            else:
                dp[next_row][next_col]=count+1
                visited[next_row][next_col]=True
                dfs(next_row,next_col,count+1)
                visited[next_row][next_col]=False
    

if __name__ == "__main__":
    sys.setrecursionlimit(10**5)
    dy=[-1,0,1,0]
    dx=[0,1,0,-1]

    n_rows,n_cols=map(int,input().split())
    board=[list(input().strip()) for _ in range(n_rows)]

    visited=[[False] * n_cols for _ in range(n_rows)]
    dp=[[0] * n_cols for _ in range(n_rows)]
    max_count=0

    dfs(0,0,0)
    print(max_count+1)