[union find path compression] 아리스, 청소합니다 (Hard)

 

문제

- 아리스, 청소합니다 Easy 버전

https://www.acmicpc.net/problem/31404

31404번: 아리스, 청소합니다! (Easy)

 

- 아리스, 청소합니다 Hard 버전 (크기 빼고, Easy와 완전 동일)

https://www.acmicpc.net/problem/31399

31399번: 아리스, 청소합니다! (Hard)

 

Easy와 달리 Hard에서는 방의 크기가 1024x1024로 확장되고, 시간 복잡도를 만족시키기 위해서 단순 시뮬레이션 외의 기법이 필요하다.

아이디어를 생각해내는 것 자체는 어렵지 않지만, 처음 풀어보는 경로 압축 문제라 푸는데 꽤 많은 시간이 걸렸었다.

 

 

풀이

알고리즘 : 구현 + 시뮬 + 스택 + 경로 압축

풀이 방법 : Easy와 동일하지만, 반복적으로 진입하는 좌표에 대해 한 번에 최종 좌표로 이동시키면서 시뮬레이션 하면 된다.

 

- 경로 압축을 위한 warp

Node warp[1024][1024][4];	// y, x, 해당 좌표에 진입한 방향
long long warpCost[1024][1024][4];	// 각 warp 시 더해줄 비용(warp 함으로써 지나친 경로의 개수)
stack<Node> memory;	// warp 배열 업데이트를 위한 지나온 경로를 기록할 자료구조

 

 

- 초기 값 (초기에는 자기 자신을 가리킴)

warp[i][j][k] = { i, j, k };
warpCost[i][j][k] = 0;

 

 

- 만약 이미 청소한 구역이라면, 지나온 간선에 기록하고, 워프가 존재한다면 warp 시도

memory.push({ y, x, d });
if (warpCost[y][x][d] > 0)
{
	Node w = warp[y][x][d];
	cnt += warpCost[y][x][d];
	y = w.y;
	x = w.x;
	d = w.d;
}

 

 

-  만약 청소하지 않는 구역에 도달하면, 그동한 기록한 간선의 최종 좌표를 현재 좌표로 재설정, 비용 재계산

long long wc = warpCost[y][x][d] + 1;
while (!memory.empty())
{
	Node tmp = memory.top();
	memory.pop();
	warp[tmp.y][tmp.x][tmp.d] = warp[y][x][d];  //warp 지점 재설정
	warpCost[tmp.y][tmp.x][tmp.d] += wc;    //warp 비용 재설정
	wc = warpCost[tmp.y][tmp.x][tmp.d] + 1; //다음칸에 대해 워프비용 재계산
}

 

 

예시

- 다음과 같이 아리스가 움직일 때, 간선의 업데이트

0 - 2 : 워프로 이동, 2 - 3, 3 - 4 : 단순 이동

 

현재 warp 배열과, 위와 같이 이동 후의 stack 상태

 

배열 업데이트 후

(warp 목적지) = (최종 목적지, root)

(최종 cost) = (기존의 cost) + (직전 노드의 cost) = (0 - 2 비용) + (2 - 4 비용)

 

 

Etc. 비슷한 유형

자료 구조 + 유니온 파인드

https://www.acmicpc.net/problem/3830

3830번: 교수님은 기다리지 않는다

https://www.acmicpc.net/problem/9938

9938번: 방 청소