백준 17090 미로 탈출하기

https://www.acmicpc.net/problem/17090
bfs 사용 시 내 머리가 꼬일 것 같아서 관뒀다.
정점에 주어진 방향이 정해져 있기 때문에 얌전히 dfs 썼다.

탐색 시 두 가지 경우로 나뉜다.
탈출 가능한 정점인 경우:
escape를 갱신한다.

다른 정점으로 이동하는 경우:
다른 정점을 탐색한 후 해당 결과를 현재 정점에도 적용한다.

dfs는 재귀 또는 스택으로 구현되므로 이를 이용한다.

이미 탐색한 정점에 대한 경우에는 그 정점의 escape 상태를 반환한다.
만약 사이클이 존재할 경우 사이클이 완성될 시 escape가 False인 상태로 탐색이 종료된다.

2중 for문을 사용해 모든 정점을 탐색해준다.
이미 탐색한 정점인 경우 즉시 escape의 상태를 반환하므로 빠르게 탐색 가능하다.

import sys
sys.setrecursionlimit(10**6)
def input(): return sys.stdin.readline().rstrip()

def solve(x, y):
    if visited[x][y]: return escape[x][y]
    
    idx = com.index(maze[x][y])
    visited[x][y] = True
    mx = x+dx[idx]
    my = y+dy[idx]
    if mx < 0 or mx >= n or my < 0 or my >= m:
        escape[x][y] = True
    elif solve(mx, my):
        escape[x][y] = True
    
    return escape[x][y]

com = ['U', 'D', 'R', 'L'] #comparison
dx = [-1, 1, 0, 0]
dy = [0, 0, 1, -1]

n, m = map(int, input().split())
maze = [list(input()) for _ in range(n)]
visited = [[False]*m for _ in range(n)]
escape = [[False]*m for _ in range(n)]
cnt = 0
for i in range(n):
    for j in range(m):
        if solve(i, j):
            cnt += 1

print(cnt)