[백준] 16724. 피리 부는 사나이 - Python

[Gold III]

 

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

16724번: 피리 부는 사나이

 

풀이

Union-Find(Disjoint Set)를 이용하여 풀 수 있는 문제라는 것만 캐치한다면, 어렵지 않게 풀이할 수 있었던 문제.

 

NxM 지도의 각 칸에 번호를 지정하고, (좌표가 r, c 일 때, 칸의 번호를 r * M + c 로 지정.)

그 번호를 기반으로 root를 저장하는 dictionary를 초기화.

 

Union, Find 함수를 구현한 후엔,

지도의 모든 칸을 순회하며, 그 칸의 진행 방향(R, L, U, D)에 따라, 다음 칸과 union해 준다. (line 43~45)

 

그 이후에는, 접근할 수 있는 칸들끼리는 Union이 되어 있는 상태이다.

따라서, 모든 칸에 대해 다시 순회하며, 동일한 root를 가진 칸은 제외, 서로 다른 root를 가진 칸의 집합의 개수를 센다.

결국, Disjoint Set의 개수를 세면 된다.

그렇다면, 그 Disjoint Set들의 root인 칸에 Safe Zone을 만들면 문제가 해결된다.

 

** EX. (예제 입력 1)

예제 입력 1의 모든 칸에 번호를 매기면 아래와 같다.

0  1  2  3
4  5  6  7
8  9  10 11

이후, 모든 칸을 순회하며 union을 진행한 후엔, 모든 칸의 root의 번호 (find(x)의 결과)는 다음과 같다.

0  0  0  0
0  5  5  0
0  0  0  0

따라서, root가 0인 Set과 root가 5인 Set. 2개로 묶였으므로, 각 Set의 어디에든 Safe Zone을 하나씩 설치하면 된다.

 

AC.

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

g = []
for _ in range(N):
    g.append(list(input()))
    
# 좌표가 [r][c]일 때, 임의로 칸의 번호를 `r * M + c` 로 지정.
root = {i: i for i in range(N*M)}

def find(x):
    if root[x] == x:
        return x
    root[x] = find(root[x])
    return root[x]

def union(x, y):
    rx = find(x)
    ry = find(y)
    if rx < ry:
        root[ry] = rx
    else:
        root[rx] = ry

def go(r, c):
    nowIndex = r*M+c
    if g[r][c] == "R":
        if c == M-1:
            return
        union(nowIndex, nowIndex+1)
    elif g[r][c] == "L":
        if c == 0:
            return
        union(nowIndex, nowIndex-1)
    elif g[r][c] == "U":
        if r == 0:
            return
        union(nowIndex, nowIndex-M)
    elif g[r][c] == "D":
        if r == N-1:
            return
        union(nowIndex, nowIndex+M)

for r in range(N):
    for c in range(M):
        go(r, c)

result = {}
for r in range(N):
    for c in range(M):
        nowIndex = r*M+c
        result[find(nowIndex)] = 1

print(len(result))