[백준] 16724번 : 피리부는사나이

16724번: 피리 부는 사나이

16724번: 피리 부는 사나이

🤔 문제분석

서로소 집합을 활용하여 문제를 해결하였습니다. 사이클이 생기는 집합을 만들고, 그 집합의 총 개수를 구하면 됩니다. 사이클이 생기는 그룹의 집합안에서 어느한곳이 막힌다면 움직이지 못하기 때문입니다. 유니온-파인드로 사이클을 모두 하나의 집합으로 만들어주고 그 집합의 개수를 새면 됩니다.

💻 코드

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
table = [list(map(str, input().strip())) for _ in range(N)]
direction = ['U', 'D', 'L', 'R']
move = [(-1, 0), (1, 0), (0, -1), (0, 1)]
parent = [i for i in range(N*M)]

def find(v1):
    if parent[v1] != v1:
        parent[v1] = find(parent[v1])
        return parent[v1]

    return parent[v1]

def union(v1, v2):
    p1 = find(v1)
    p2 = find(v2)
    
    if p1 > p2:
        parent[p1] = p2
    else:
        parent[p2] = p1
        
def start(i, j):
    index = direction.index(table[i][j])
    dy, dx = move[index]
    ny, nx = dy + i, dx + j
    v1 = i*M + j%M
    v2 = ny*M + nx%M
    p1 = find(v1)
    p2 = find(v2)
    if p1 == p2:
        return
    else:
        union(p1, p2)
        start(ny, nx)
        return

for i in range(N):
    for j in range(M):
        start(i, j)
        
print(len(set(parent)))

🎯 피드백 및 개선사항

너비우선탐색, 깊이우선탐색으로도 방문처리를 활용하여 문제를 해결할 수 있습니다.