백준 - 1103 게임

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

문제 요약

1. N * M 문자열에 숫자 혹은 구멍(H)가 존재한다.
2. 현재 위치의 숫자만큼 동서남북으로 이동할 수 있다. 이동할 때 구멍은 무시한다.
3. 만약 도착한 곳이 문자열 밖이거나, 구멍이면 게임이 끝난다.
4. 이동할 수 있는 최댓값을 구하라 (무한대라면 -1)

풀이 요약

1. Dp 배열에 현재 위치에 도달할 수 있는 최댓값을 저장한다. (global scope)
2. 방문배열을 만들어 해당 위치에 도달했는지 여부를 확인한다. (백트래킹처럼)
3. 다음에 갈 곳이 범위 안이고, 구멍이 아니면 그리고 dp배열값 최댓값을 갱신할 수 있으면 재귀를 돈다.
4. 단, 해당 재귀에서 방문했었다면, return한다.(사이클이 생겨서 최댓값이 무한대다.)

코드

n,m = map(int,input().split())
game = list()
for _ in range(n) :
    game.append(list(input()))

# 사이클을 확인할 flag
flag = False
# 이동값을 저장할 dp배열
dp = [[0]*m for _ in range(n)]
# 사이클을 확인할 방문 배열
v = [[0]*m for _ in range(n)]
# 이동방향을 정해줄 배열
dr = [1,-1,0,0]
dc = [0,0,1,-1]

answer = -1


def dfs(r, c, cnt) :
    global flag, answer
    # answer은 항상 최댓값으로 갱신
    answer = max(answer, cnt)
    
    #만약 사이클이 있다면
    if flag :
        return
    for d in range(4) :
        nr = dr[d]*int(game[r][c]) + r
        nc = dc[d]*int(game[r][c]) + c
        if 0 <= nr < n and 0 <= nc < m and game[nr][nc] != "H" and dp[nr][nc] < cnt + 1:
            # 방문했던 곳을 다시 방문한다면 해당 재귀에 사이클이 있다는 말!
            if v[nr][nc] :
                flag = True
                return
            #만약 모든 조건에 적합하다면
            v[nr][nc] = 1
            dp[nr][nc] = cnt+1
            dfs(nr,nc,cnt+1)
            # 방문배열을 다시 초기화하면서 다음 재귀에 영향가지 않도록 한다.
            v[nr][nc] = 0

v[0][0] = 1
dfs(0,0,1)
if flag :
    print(-1)
else :
    print(answer)

후기

1. 꽤 문제를 오래 풀었는데, 초기 코드는 빠르게 나왔지만, dfs if문에 문제가 있었다.

if 0 <= nr < n and 0 <= nc < m and game[nr][nc] != "H" and dp[nr][nc] < cnt + 1:    
	if v[nr][nc] :
    	flag = True
        return
    v[nr][nc] = 1
    dp[nr][nc] = cnt+1
    dfs(nr,nc,cnt+1)
    v[nr][nc] = 0

이 부분이 원래는

if 0 <= nr < n and 0 <= nc < m :    
	if game[nr][nc] == "H" :
    	continue
    if v[nr][nc] :
    	flag = True
        return
    if dp[nr][nc] > cnt + 1 :
    	return
        .
        .
        .  

이렇게 되어있었는데 불필요한 재귀가 많이 돌았던 것

2. 사이클 생기는 지 여부를 flag로 파악했는데 다른 코드를 보니 사이클이 생긴순간 print(-1)하고 exit()를 하면 되더라....는 걸 배웠다.