16724: 피리 부는 사나이

문제 링크

16724: 피리 부는 사나이

구현 방식

• 성우가 정해놓은 방향대로 움직이면서, 몇개의 cycle이 발생하는 지를 찾는 find-union 문제이다
• find-union 수행 시 parent는 1차원으로 정의되므로 x = idx//M; y = idx%M 이런 식으로 차원을 낮춰주는 처리가 필요하다
• 마지막에 parent 리스트에서 집합의 개수를 찾기 전에 한번 find를 쭉 수행해주어 최상단의 노드들까지 갱신해줘야한다

코드

import sys

dx = (0, 0, -1, 1)
dy = (-1, 1, 0, 0)

N, M = map(int, sys.stdin.readline().strip().split())
board = [list(sys.stdin.readline().strip()) for n in range(N)]

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

def union(a, b):
    a = find(a); b = find(b)
    if a < b: parent[b] = a
    else: parent[a] = b

parent = [i for i in range(N*M)]
for idx in range(N*M): #find-union 수행
    x = idx//M; y = idx%M
    direction = -1
    if board[x][y] == 'D': direction = 3
    elif board[x][y] == 'U': direction = 2
    elif board[x][y] == 'R': direction = 1
    elif board[x][y] == 'L': direction = 0

    nx, ny = x + dx[direction], y + dy[direction]
    if 0<=nx<N and 0<=ny<M:
        nidx = nx*M + ny
        if find(idx) != find(nidx): union(idx, nidx)

for idx in range(N*M): find(idx)
print(len(set(parent)))