백준 16724 피리 부는 사나이 문제 풀이
백준 온라인 저지, 16724번: 피리 부는 사나이
도입
제시되는 모든 타일은 이동 방향을 지시하고 있다. 즉 어떠한 타일에 위치하든 회원들은 계속해서 일정한 경로를 순회하거나, 벽(맵의 바깥)에 막혀 이동이 정지될 것이다.
일정한 경로를 순회하도록 하는 타일의 집합도, 특정한 목적지가 있는 타일의 집합도 모두 각각 그룹화할 수 있다.
문제 풀어보기
타일들을 단일 그룹으로 생각할 수 있다면, 각 그룹마다 ‘SAFE ZONE’을 한 개씩 배치하면 문제의 목표를 달성할 수 있다. 즉, “타일 그룹”의 개수를 세는 것으로 문제를 해결한다.
어떤 대상을 임의의 기준에 따라 그룹으로 적절히 묶어내는 데는 유니온-파인드가 유용하다.
모든 타일을 단 한번만 처리한다면 일정한 경로를 순회하는 “타일 그룹”도 유니온-파인드에서의 부모를 어려움 없이 정할 수 있다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
# parents[idx]; idx = (y) * m + (x)
parents = [i for i in range(n * m)]
def merge(a: int, b: int):
pa, pb = find(a), find(b)
if pa < pb:
parents[b] = pa
else:
parents[a] = pb
def find(n: int) -> int:
if parents[n] == n:
return n
return find(parents[n])
주의할 것은 가장 개념적이고 단순한 유니온-파인드 구현은 “순회하는 타일 그룹”에 있어 큰 오버헤드가 발생할 수 있다는 것이다.
근원, 다시 말해 최상위 부모 정보를 갱신하지 않으면 한번 부모를 찾을때마다 부모의 부모, 부모의 부모의 부모…를 계속해서 참조하며 최상위 부모를 찾게 된다.
그 이전에 만약 0번 인덱스부터 9번 인덱스까지 서로 순회하는 타일이 있다면, 코드는 부모를 [1, 2, 3, 4, 5, 6, 7, 8, 9, 0, ..]로 기록하여 최대 재귀 깊이까지 탐색하다 RecursionError와 함께 종료할 것이다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def merge(a: int, b: int):
pa, pb = find(a), find(b)
if pa < pb:
parents[pb] = pa
parents[b] = pa
else:
parents[pa] = pb
parents[a] = pb
def find(n: int) -> int:
if parents[n] == n:
return n
p = find(parents[n])
parents[n] = p
return p
따라서 위와 같은 방법으로 순환 참조를 막는다.
1
[0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0]
유니온-파인드로 타일을 적절히 그룹화했다면, 부모 목록에는 각 그룹의 대표 타일 인덱스만 남아있을 것이므로 이를 적절히 사용하여 그룹의 개수를 찾아내어 해결할 수 있다.