[백준 파이썬] 16724 피리 부는 사나이

백준 16724

벽 끝으로 간다면 알아서 멈추겠지만 방향 지도에서 루프가 생겨버리면 멈추지 못하고 계속 돌게 된다. 만들어진 루프마다 safe zone을 만들어 준다.
사이클을 찾는 다른 문제인 백준 9466 텀 프로젝트와 같은 방법으로 푼다.

N, M = map(int, input().split())
maps = [list(input()) for _ in range(N)]

visited = [[0 for _ in range(M)] for _ in range(N)]
safe_zone = 0

def dfs(x, y):
    global safe_zone
	
    # 현재 위치 방문처리
    visited[y][x] = True
    # 사이클에 현재 위치 추가
    cycle.append([x, y])
    
    if maps[y][x] == 'U' and y > 0: # 위로
        y -= 1
    elif maps[y][x] == 'D' and y < N-1: # 아래
        y += 1
    elif maps[y][x] == 'L' and x > 0: # 왼쪽
        x -= 1
    elif maps[y][x] == 'R' and x < M-1: # 오른쪽
        x += 1

    if visited[y][x]: # 이동한 위치를 이미 방문한 경우
        if [x, y] in cycle: # 사이클에 이 위치가 포함되어 있다면
            safe_zone += 1 # 사이클이 생겼으므로 세이프 존을 설치해야한다.
    else: # 방문안했으면 다음 위치로
        dfs(x, y)

for x in range(M):
    for y in range(N):
        if not visited[y][x]:
            cycle = []
            dfs(x, y)
            
print(safe_zone)