§ 1문제 정의
기기에서 송출한 신호는 벽을 만나면 절반으로 약해진다. 신호가 도달했다는 사실 자체가 “같은 방”의 증거. 받은 power가 0보다 크면 union, 같은 그룹.
스마트한 풀이는 power를 점점 키워가며 union-find를 한다 — 작은 power로 가까운 형제부터 묶고, 끝까지 미루다 power 1000을 한 번도 호출하지 않게 한다. 비용 함수가 power³이라 30 → 1000은 약 37,000배 차이.
마지막에 “루트만 한 번 더 195로 스캔”하는 패턴이 결정타다. 그룹의 대표 노드만 검사하면 분산된 부분 그룹들을 마저 묶을 수 있고, 추가 비용은 미미하다.
power³은 단호한 비용 함수다. 작게 시작해서, 작게 끝내라.
§ 2예제 시각화 — 4개 방, 12개 기기
FIG. 4 — power-laddered union-find
STEP 01 / 6
SPACE play/pause · ← → step · R reset
§ 3알고리즘 골격
scan(firstID, totalDevices):
for power in [30, 60, 100, 300, 600, 1000]:
for each known device d:
detected = scan_device(d, power, …)
for r in detected:
if r.power > 1 and r.range == power:
union(d, r.id)
if all devices grouped: break
# 마지막 단계: 루트만 power=195로 한 번 더
for each root r:
detected = scan_device(r, 195, …)
for x in detected: union(r, x.id)