[Python 3] BOJ - 17090 "미로 탈출하기"

 # 문제 링크

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

17090번: 미로 탈출하기

 

 # 풀이

 개인적으로 이 문제의 핵심은 다이나믹 프로그래밍이라고 생각한다. 상태 공간을 현재 (x, y)일 때 밖으로 나갈 수 있는지 여부로 정의한다.

<그림 1. 예제 4의 경우>

 위 그림 1은 예제 4의 경우를 나타낸 그림이다. 빨간색이 현재 위치, 파란색 위치가 다음 위치일 때 상태이다. 만일 현재 위치를 한번도 방문하지 않는다면 -1, 처음 방문한다면 0으로 초기화한다. 만일 범위 밖으로 나간다면 1을 리턴함으로서 전체 경로를 1로 변경한다. 마지막의 경우는 이미 방문했으나 밖으로 나갈 수 없기 때문에 상태 공간의 탐색을 종료한다.

 따라서, 현재 (0, 0)으로 이어지는 모든 경로는 밖으로 나갈 수 있는지 없는지의 여부가 갱신되었기 때문에 방문 하지 않은 위치인 (0, 3)에서 다시 상태 공간을 탐색한다.

<그림 2. 예제 4의 경우>

 위 그림 2는 그림 1과 달리 밖으로 나가는 경로를 찾은 경우이다. 만일 현재의 위치가 밖이라면 1을 리턴하여 현재 위치까지 오기 위한 모든 경로에 1로 갱신한다. 따라서 점화식은 아래와 같다. $$dp[x][y] = max(dp[x][y], \ value) \ if \ outside, \ val = 1 \ else \ val = 0)$$ 따라서, 현재 방문하지 않았다면 리턴값이 0이 아닌 블록을 모두 세어주고, 방문했다면 상태 배열값이 0이 아닌 블록을 모두 세어주면 정답을 구할 수 있다.

 

 # 코드

import sys

# 재귀깊이 해제
sys.setrecursionlimit(600000)

# go : 현재 위치가 (i, j)일 때 밖으로 나가는 경로의 일부라면 1, 아니면 0을 리턴하는 함수
def go(i, j):
    # Base case : 밖으로 나가는 경우
    if i < 0 or i > n - 1 or j < 0 or j > m - 1:
        return 1
    # Memoization
    if dp[i][j] != -1:
        return dp[i][j]
    dp[i][j] = 0
    # 점화식
    dp[i][j] = max(dp[i][j], go(i + cache[arr[i][j]][0], j + cache[arr[i][j]][1]))
    return dp[i][j]

# 입력부
n, m = map(int, sys.stdin.readline().split())
arr = [list(sys.stdin.readline().rstrip()) for _ in range(n)]

# dp : 2차원 상태 공간 배열
dp = [[-1] * m for _ in range(n)]

# cache : 현재 위치가 가리키는 방향을 key, 그 때 가야할 칸 수를 value로 갖는 dictionary
cache = {'L' : (0, -1), 'R' : (0, 1), 'U' : (-1, 0), 'D' : (1, 0)}
ans = 0

for i in range(n):
    for j in range(m):
        # 아직 방문하지 않은 경우
        if dp[i][j] == -1:
            # 밖으로 갈 수 있다면 정답 증가
            if go(i, j) != 0:
                ans += 1
        # 방문했고 밖으로 나갈 수 있는 경우 정답 증가
        elif dp[i][j] == 1:
            ans += 1
            
# 정답 출력
print(ans)