백준 1103 - 게임

27 Aug 2021 | dfs dp

https://www.acmicpc.net/problem/1103

처음에는 트리의 max depth를 구하는 문제라고 생각했다.

여기에 조건으로 cycle 유무만 체크해주는 방식으로 풀었다.

결론은 시간 초과이다. 아직 복잡도 계산하는게 익숙치 않아서 왜 시간 초과인지는 모르겠다.

def dfs(x,y,cnt):

    global ans
    ans = max(ans, cnt)

    for i in range(4):
        nx = x+int(graph[x][y])*dx[i]
        ny = y+int(graph[x][y])*dy[i]

        if 0<= nx < n and 0 <= ny < m and graph[nx][ny] != 'H':
            if visited[nx][ny]: # cycle
                print(-1)
                exit()
            else:
                visited[nx][ny] = True
                dfs(nx,ny,cnt+1)
                visited[nx][ny] = False # dfs내의 한 방향 depth일 때만 재귀 체크 해야돼서 재귀 끝나면 해제


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

n, m = map(int, input().split())
graph = [input() for _ in range(n)]
visited = [[False]*m for _ in range(n)]
ans = 0
dfs(0,0,0)

print(ans+1)

문제를 보니까 메모리를 512MB나 줘서 brute force하지말고 dp로 연산량 줄여가면서 풀라는 것 같았다.

따라서 아래와 같은 방식으로 탐색의 조건을 추가해줬다.

import sys
sys.setrecursionlimit(10**6) # recursion limit 늘려줌 안하면 runtime error

def dfs(x,y,cnt):
    
    global ans
    ans = max(ans, cnt)

    for i in range(4):
        nx = x+int(graph[x][y])*dx[i]
        ny = y+int(graph[x][y])*dy[i]

        if 0<= nx < n and 0 <= ny < m and graph[nx][ny] != 'H' and cnt+1>dp[nx][ny]:
            if visited[nx][ny]: # cycle
                print(-1)
                exit()
            else:
                dp[nx][ny] = cnt+1
                visited[nx][ny] = True
                dfs(nx,ny,cnt+1)
                visited[nx][ny] = False


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

n, m = map(int, input().split())
graph = [input() for _ in range(n)]
visited = [[False]*m for _ in range(n)]
dp = [[0]*m for _ in range(n)]
ans = 0
dfs(0,0,0)

print(ans+1)

Related Posts

Comments