[백준]1103 게임

0. 풀이 원칙

※ dfs,dp류의 문제는 아래와 같은 원칙을 기본적으로 따른다.

(1) dp 리스트를 -1로 초기화 한다.

(2) 처음방문했을 때 0으로 바꿔준다

(3) 끝까지 간 다음 리턴값을 적절히 조정한다. 이때 리턴은 현재 depth에서 r,c의 상태를 판단하는 방식으로 아래와 같이 구성한다. (bfs를 수행할 때 queue에 넣기위해 미리 tempR,tempC를 검사하는것과 다르다. 일딴 재귀를 돌돌리고 검사한다.)

    if not (0 <= r < N and 0 <= c < M):
        return 0
    # 구멍이면
    if L[r][c] == "H":
        return 0

# dfs로 사이클 확인

모든 검사가 끝난 후(현재 depth에서 재귀가 모드 끝난 후) fin을 처리해준다.

        for k in range(4):
            tempR = r + dR[k] * int(L[r][c])
            tempC = c + dC[k] * int(L[r][c])
            # 첫방문
            dp[r][c] = max(dp[r][c], dfs(tempR, tempC) + 1)
        fin[r][c]=1
        return dp[r][c]

 

1. 풀이

1520 내리막길(dfs,dp) 와 9466텀프로젝트(dfs,사이클확인)를 합친문제.

(1) 처음 방문시 dp[i][j]를 -1에서 0으로 초기화.

(2) 끝까지 도달했을 때 끝났음을 의미하는 fin[r][c]=1 수행

(3) r,c를 방문했을 때 경우의 수는 다음과 같다

-범위밖 or 구멍에빠짐 -> 0을리턴

-범위안

- 방문한적 있음

- 현재경로에서 방문 -> -1출력

- 이전경로에서 방문 -> dp 리턴

- 방문한적없음 -> 4방향조사

​

2. 소스코드

(1) 방문했을때 0으로 바뀌는걸 이용하여 사이클판단, 틀림

처음에 방문했을 때 dp가 -1에서 0으로 바뀌는것을 이용하여 사이클이 있는지 확인하려고 했다.

dp는 끝까지 간 다음 return값을 주기 때문에, 끝까지 가기 전까진 0을 유지한다.

따라서 r,c를 방문했는데 dp[r][c]가 0이면 현재 경로가 끝나지도 않았는데 다시 방문한것으로 판단할 수 있다고 생각했다.

​

r,c를 방문했는데, dp[r][c]가 0이면 사이클이 맞긴하다. 하지만 0이 아니라도 사이클일 수 있다.

이유는 r,c에서 네방향을 이동할 때, 빨리 떨어지는 쪽을 먼저 방문하면 dp가 return을 받아버리므로, 0이 아닌값을 가지게 되기 때문이다.

즉 운좋게 탐색할 수 있는 가장 깊은곳을 먼저 탐색한다면 dp[r][c]==0으로 사이클을 확인할 수 있지만, 그렇지 않은 경우는 위와같은 방법으로 사이클을 판단할 수 없다.

[반례]

5 5
13HH2
2HHHH
HHHH2
HHHHH
3HHH4

import sys
sys.setrecursionlimit(10**6)
N, M = map(int, input().split())
dR = [0, 0, -1, 1]
dC = [1, -1, 0, 0]


def dfs(r, c):
    '''
    print(r,c)
    for i in dp:
        print(i)
    '''
    # 바깥으로 나가거나 구멍에 빠지면
    if not (0 <= r < N and 0 <= c < M):
        return 0
    # 구멍이면
    if L[r][c] == "H":
        return 0
    # 방문한적없음
    if dp[r][c]==-1:
        dp[r][c]=0
        for k in range(4):
            tempR = r + dR[k] * int(L[r][c])
            tempC = c + dC[k] * int(L[r][c])
            # 첫방문
            dp[r][c] = max(dp[r][c], dfs(tempR, tempC) + 1)
        return dp[r][c]
    # 방문한적있음
    else:
        # 사이클있음
        if dp[r][c] == 0:
            print(-1)
            sys.exit()
        else:
            return dp[r][c]

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

ans = 0
dp = [[-1 for j in range(M)] for i in range(N)]
print(dfs(0, 0))
'''
for i in dp:
    print(i)
'''

 

(2) fin 리스트를 이용하여 방문여부확인, 정답

import sys
sys.setrecursionlimit(10**6)
N, M = map(int, input().split())
dR = [0, 0, -1, 1]
dC = [1, -1, 0, 0]
def dfs(r, c):
    '''
    print(r,c)
    for i in dp:
        print(i)
    '''
    # 바깥으로 나가거나 구멍에 빠지면
    if not (0 <= r < N and 0 <= c < M):
        return 0
    # 구멍이면
    if L[r][c] == "H":
        return 0
    # 방문한적없음
    if dp[r][c]==-1:
        dp[r][c]=0
        for k in range(4):
            tempR = r + dR[k] * int(L[r][c])
            tempC = c + dC[k] * int(L[r][c])
            # 첫방문
            dp[r][c] = max(dp[r][c], dfs(tempR, tempC) + 1)
        fin[r][c]=1
        return dp[r][c]
    # 방문한적있음
    else:
        # 사이클있음
        if not fin[r][c]:
            print(-1)
            sys.exit()
        else:
            return dp[r][c]

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

ans = 0
dp = [[-1 for j in range(M)] for i in range(N)]
fin =[[0 for j in range(M)] for i in range(N)]
print(dfs(0, 0))
'''
for i in dp:
    print(i)
'''