백준 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]
유니온-파인드로 타일을 적절히 그룹화했다면, 부모 목록에는 각 그룹의 대표 타일 인덱스만 남아있을 것이므로 이를 적절히 사용하여 그룹의 개수를 찾아내어 해결할 수 있습니다.