백준 16724 피리 부는 사나이 python

문제로이동

16724번: 피리 부는 사나이

---

목차

 

---

 

---

문제 설명

틀렸습니다*3

Union-Find를 하며 주의해야 할 점이 parent에 직접 접근을 하게 되면 미처 업데이트 되지 않았던 값들이 있기에 반드시 getParent로 접근을 해야하는데 이를 놓쳐버렸습니다😅

접근 방법

문제 방향을 잡는데 5분 가량 걸렸습니다. 처음엔 필드에 적힌대로 이리 저리 따라가다가, Union-Find라는 것을 알게 되었습니다!

이 문제를 푸는데 있어서 가장 중요한 것은 구역 입니다.

사이클이 형성된다면 그것은 같은 구역입니다.

 

입력 예제를 볼까요?

예제 입력 초기 세팅

사이클이 형성되는 것을 살펴보고 바로 구역을 나눠봅시다.

임의의 위치에서 하나씩 손으로 방향을 따라가보시는게 빠릅니다.

 

1. 첫번째 사이클(구역) 형성

 

2. 두번째 사이클(구역) 형성

 

이렇게 해당 예제는 2가지 사이클이 생성됩니다.

각 구역(사이클) 내에 어떤 위치던 상관 없이 SAFE ZONE이 있다면 모두 처리가 완료되겠죠?

 

즉, 우리는 구역의 갯수만 파악한다면 이 문제를 쉽게 맞출 수 있습니다!!

 

어, 좌표값인데 어떻게 union-find를 적용하지?

Union-Find를 할 때 각 공간에 임의의 번호를 새길 수 있다면 편하겠죠?

왜냐면 대부분의 Union-Find 문제는 parent라는 배열을 생성후 index를 매겨줬으니까요

 

# num : 각 배열의 고유 번호
# next_num : 다음에 이동할 목적지 번호

x = num%M
y = num//M
cur = field[y][x]
nx = x+direction[cur][0]
ny = y+direction[cur][1]    
next_num = ny*M + nx

 

배열에서 굉장히 유용하게 쓰이는 방법이라 혹시 모르셨다면 이번 기회에 짚고 넘어 가시면 좋을 것 같습니다.

이제 x, y 좌표만으로 각 위치에 해당하는 index를 파악할 수 있게 되었습니다.

 

구역의 갯수 파악

저는 python dictionary, java로 따지면 hashmap을 이용했습니다.

visited = dict()
for i in range(N*M):
    if getParent(parent[i]) not in visited:
        answer+=1
        visited[parent[i]]=True

 

등록되지 않은 parent라면 새롭게 등록을 해주고 정답의 갯수를 증가시킵니다.

---

소스 코드

Python

import sys
input =sys.stdin.readline
direction = dict()
direction['D']=[0,1]
direction['L']=[-1,0]
direction['R']=[1,0]
direction['U']=[0,-1]
N,M = map(int,input().split())
field = [list(input().strip()) for _ in range(N)]
parent = [i for i in range(N*M)]

def getParent(x):
    if x==parent[x]:return x
    parent[x] = getParent(parent[x])
    return parent[x]
def unionParent(a,b):
    a=getParent(a)
    b=getParent(b)
    if a==b:return
    if a<b:parent[b]=a
    else:parent[a]=b

for num in range(N*M):
    x = num%M
    y = num//M
    cur = field[y][x]
    nx = x+direction[cur][0]
    ny = y+direction[cur][1]    
    next_num = ny*M + nx
    if next_num<0 or next_num >= N*M:continue
    unionParent(num,next_num)
answer = 0
visited = dict()
for i in range(N*M):
    if getParent(parent[i]) not in visited:
        answer+=1
        visited[parent[i]]=True
print(answer)

---

Java8

#