[백준] 16624번 피리 부는 사나이 _ Python

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

16724번: 피리 부는 사나이

 

 

---

 

1. Preview

풀이 시간: 35분 + 30분

시간 복잡도: O(NM)

공간 복잡도: O(NM)

 

 

---

 

2. 초기 접근 방법

board[][] 에서 모두 방문하는데 "dfs 탐색를 진행한 횟수" 라고 생각해 풀었다.

 

3 4

DLLL

DDDU

RRRU

 

곰곰히 고민해보니, 위와 같은 case에서 dfs 탐색이 3번 일어나지만, 필요한 safezone은 1개이다.

 

 

---

 

3. 생각

 

그럼 어떻게 풀어야 할까?

 

각 dfs 탐색을 진행할 때마다 해당 경로에 "고유의 표식"을 남겨야 한다.

문제에서 '지도 밖으로 나가는 입력은 주어지지 않는다' 고 했으니 다시 후진을 해서라도 기존에 방문했던 노드를 다시 방문할 수 밖에 없다.

그 때, 다시 방문한 지역이 현재 경로와 일치하는지, '표식'으로 판별해 카운트 해주면 된다.

 

다시 방문한 지역이 현재 경로와 다를 시,

재방문 노드의 경로를 통해 이전에 만든 safezone으로 향하므로 별도의 카운트를 해주지 않아도 된다.

 

 

---

 

4. 코드

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

direction = ['L', 'R', 'U', 'D']
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]

def dfs(x, y, idx):
    global result

    # 이미 표식이 있는 블록이면
    if visited[x][y] != -1:
        if visited[x][y] == idx:
            result += 1
        return

    visited[x][y] = idx # 표식
    k = direction.index(board[x][y])
    dfs(x + dx[k], y + dy[k], idx)


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

visited = [[-1] * M for _ in range(N)]

result = 0
dfsCount = 0
for i in range(N):
    for j in range(M):
        if visited[i][j] == -1:
            dfsCount += 1
            dfs(i, j, dfsCount)

print(dfsCount)
print(result)