[백준 16724번] 피리 부는 사나이 (Python3)

import sys
input = sys.stdin.readline

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

MAP = []
direction = {"U":[-1,0],"D":[1,0],"R":[0,1],"L":[0,-1]}
parent = {(i,j):(i,j) for i in range(N) for j in range(M)}

def findparent(tuple):
  if parent[tuple] == tuple:
    return tuple
  else:
    parent[tuple] = findparent(parent[tuple])
    return parent[tuple]

    
for i in range(N):
  MAP.append(input().strip())

for i in range(N):
  for j in range(M):
    dy,dx = direction[MAP[i][j]]
    parent[(i,j)] = findparent((i+dy,j+dx))

cnt = 0
for i in range(N):
  for j in range(M):
    if parent[(i,j)] == (i,j):
      cnt+=1

print(cnt)

방금 전에 풀었던 사이클게임 문제와 원리가 거의 유사한 문제라 아주 쉽게 해결할 수 있었다.

 

문제의 핵심은 결국 맵 안에서 사이클의 개수를 찾으라는 의미이다. 따라서 이동해야하는 방향의 위치를 부모노드로 설정하고, 최종 부모노드가 본인인 지점이 몇개인지를 세면 그것이 곧 세이프노드를 설치해야하는 개수라고 볼 수 있다.

 

 

오늘의 교훈) 한번 공부한 알고리즘을 잘 활용하자