16724. 피리 부는 사나이 (Python)

16724번: 피리 부는 사나이

 

풀이

 dfs를 이용하여 문제를 해결할 수 있다. 방문 체크를 True, False가 아닌 숫자로 기록해준다. 처음 dfs를 할 때는 1을 기록하고 다음 dfs를 할 때는 2를 기록하는 방식으로 방문 체크를 한다. 

 2를 기록하는 dfs를 하고 있다고 가정해보자. 계속 2를 돌며 dfs를 수행하다가 2를 마주치면 이는 현재 2가 기록된 지점들에 대해서 순환 하고 있다는 뜻이다. 그렇기 때문에 2가 기록된 지점들 중 임의의 지점에 SAFE ZONE을 만들면 모든 2가 방문할 수 있는 SAFE ZONE을 만들 수 있다.

 이제 3을 기록하는 dfs를 살펴보자. 계속 3을 기록하며 dfs를 수행하다가 2가 기록된 지점에 도착했다고 가정해보자. 이는 3이 기록된 지점들은 3 자신들만 순환하는 경로가 아니라 이전에 기록된 경로에 합쳐지게 된다. 그렇기 때문에 3이 기록된 지점들을 위한 SAFE ZONE을 따로 만들 필요 없이 2의 SAFE ZONE을 이용하면 되기 때문에 새로운 SAFE ZONE을 만들지 않아도 된다.

 

 위와 같은 방법으로 dfs를 수행하면 필요한 최소 SAFE ZONE 개수를 구할 수 있다.

 

코드

import sys
input = sys.stdin.readline


# idx로 방문체크 하는 dfs 함수
def dfs(x, y, idx):
    visited[x][y] = idx  # 현재 지점의 방문 체크를 idx로 설정
    dx, dy = dist[board[x][y]]
    nx, ny = x + dx, y + dy

    if visited[nx][ny] == -1:  # 아직 방문하지 않은 지점이면 dfs 함수 호출
        dfs(nx, ny, idx)
    elif visited[nx][ny] == idx:  # 이미 방문한 지점이고 같은 idx가 기록된 곳이라면
        global cnt  # 새로운 SAFE ZONE을 만들어 줘야 한다.
        cnt += 1
        return
    else:  # 이미 방문한 지점이고 다른 idx가 기록된 곳이라면 SAFE ZONE을 만들 필요가 없다.
        return


if __name__ == '__main__':
    N, M = map(int, input().split())
    board = []
    visited = [[-1 for _ in range(M)] for _ in range(N)]  # -1 : 아직 방문하지 않은 지점
    dist = {'D': (1, 0), 'U': (-1, 0), 'L': (0, -1), 'R': (0, 1)}

    for _ in range(N):
        direction = input()
        board.append(direction)

    cnt, idx = 0, 0
    for i in range(N):
        for j in range(M):
            if visited[i][j] == -1:  # 아직 방문하지 않은 지점이면 dfs 수행
                dfs(i, j, idx)
                idx += 1

    print(cnt)