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)