[백준/dfs] 1103번: 게임

-문제: https://www.acmicpc.net/problem/1103

 

무한루프를 도는 조건이 사실 어떤 원리로 발생하는지 이해가 가지 않았다. 

찾아보니 방문했던 곳을 한번 더 방문하면 무한루프가 돌 가능성이 있어서 이것을 바탕으로 -1을 출력하면된다 

 

방문한 횟수를 dp 행렬을 따로 만들어 이용함으로써 시간초과를 방지할 수 있다고 한다 

 

마지막에 주의할 점은 ans값을 구했어도 마지막에 바깥으로 빠지거나 구멍에 빠질때도 한번 더 움직이는 것이므로 ans+1을 해주어야한다

 

참고한 블로그

-정답풀이:

import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline

n,m=map(int,input().split())
s=[list(map(str,input())) for _ in range(n)]
visit=[[0]*m for _ in range(n)]
dx=[-1,1,0,0]
dy=[0,0,-1,1]

ans=0
dp=[[0]*m for _ in range(n)]
def dfs(x,y,cnt):
    global ans
    ans=max(ans,cnt)
    visit[x][y]=1
    k=int(s[x][y])
    for i in range(4):
        nx,ny=x+dx[i]*k,y+dy[i]*k
        if 0<=nx<n and 0<=ny<m and s[nx][ny]!='H' and cnt+1>dp[nx][ny]:
            if visit[nx][ny]:
                print(-1)
                exit()
            else:
                dp[nx][ny]+=1
                visit[nx][ny]=1
                dfs(nx,ny,cnt+1)
                visit[nx][ny]=0
dfs(0,0,0)
print(ans+1)