[BOJ_Python] 16724. 피리 부는 사나이

문제

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

 

사용 알고리즘

DFS

 

풀이

고려사항

1. 현재 지나고 있는 경로의 상태

- 아직 방문한 적이 없는 곳인지

- 지금 현재 만들고 있는 경로에 있는지

- 이전에 safe zone으로 갈 수 있는 곳으로 판명한 곳인지

 

후기

1. 이 문제의 keypoint는 사이클을 추적하는 것이다.

갈 수 있는 방향이 한 개로 한정되어 있으며, 지도 밖으로 나가는 방향의 입력은 주어지지 않는다.

이러한 조건들로 인해 풀이가 간단해졌다.

 

2. 방문하지 않은 곳만 DFS를 시작하였다.

2-1) visited[ci][cj] == 0 인 경우

방문하지 않은 곳이기 때문에 진행 중인 경로로 1로 설정하고 스택에 넣어준다.

이후 방향에 따라 이동을 진행한다.

2-2) visited[ci][cj] == 1 인 경우 지금 진행중인 사이클에 safe zone이 없으므로 새로 하나 만들어주고

해당 경로는 이제 safe zone으로 갈 수 있는 곳이니

지나온 경로를 모두 safe zone에 갈 수 있음으로 변경한다.

2-3) 경로를 진행 중 safe zone에 갈 수 있는 경로와 만났다면 

기존 safe zone으로 가면 되기 때문에

새로 만들어주지 않고 경로만 모두 safe zone에 갈 수 있음으로 변경한다.

 

3. 하지만 이 방식은 방향이 1개인 경우만 가능하다.

그래프에서는 여러 방향으로 갈 수 있는 그래프가 많으니

그러한 경우에는 좋은 방법이 될 수 없다.

때문에 그런 경우는 union-find 방식을 선택하는 것이 더욱 좋아보인다.

 

코드

import sys

input = sys.stdin.readline


def find_safe_zone(ci, cj):
    global cnt
    # 이동 경로 저장할 리스트
    stack = []

    while True:
        # 아직 방문하지 않은 곳
        if visited[ci][cj] == 0:
            visited[ci][cj] = 1
            stack.append((ci, cj))
			
            # 방향에 맞춰 이동
            if arr[ci][cj] == "U":
                ci -= 1
            elif arr[ci][cj] == "D":
                ci += 1
            elif arr[ci][cj] == "L":
                cj -= 1
            else:
                cj += 1

        # 지금 진행하고 있는 사이클 -> cnt 늘려주기
        elif visited[ci][cj] == 1:
            visited[ci][cj] = 2
            cnt += 1
            for ti, tj in stack:
                visited[ti][tj] = 2
            break

        # 세이프존으로 이동가능한 길 -> cnt 변화없음(기존 safe zone 사용)
        else:
            visited[ci][cj] = 2
            for ti, tj in stack:
                visited[ti][tj] = 2
            break

    return


N, M = map(int, input().split())

arr = [list(input().rstrip()) for _ in range(N)]

# 방문여부 확인 리스트 
# (0: 아직 방문하지 않은 곳, 1: 현재 진행중인 경로, 2: safe zone으로 갈 수 있는 경로)
visited = [[0] * M for _ in range(N)]

# safe zone의 갯수
cnt = 0

for i in range(N):
    for j in range(M):
        # 아직 방문하지 않았다면 safe zone 찾기
        if visited[i][j] == 0:
            find_safe_zone(i, j)

print(cnt)

 

결과