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

문제링크:

 

실시간으로 x, y, z 가 입력된다. 이 말은 x 보다 y 가 z 만큼 무겁다는 뜻이다.

중간중간 쿼리 a, b 가 입력된다. 이 때 우리는 a 보다 b 가 얼마나 무거운지 출력해야 한다.

샘플은 최대 10만개, 쿼리와 무게관계도 최대 10만개 입력된다.

 

이 문제는 개인적으로 굉장히 좋은 문제라고 생각한다.

우선 Union-Find 와 관련있다는 것은 금방 관찰할 수 있다.

 

x y z 가 입력이 되면, x 와 y 는 서로 무게 차이를 알아낼 수 있는 관계가 된다.

그 말은, x 와 서로 무게 차이를 알아낼 수 있는 샘플은 y 와도 서로 무게 차이를 알아낼 수 있다는 것이다.

따라서 쿼리 a, b 가 입력됐을 때, a 와 b 가 연결되지 않았으면 UNKNOWN 이 답이다.

 

하지만 이 문제는 단순한 Union - Find 가 아니다.

물론 N이 10만이기 때문에 경로 압축을 해야 하지만, 경로가 압축이 되면서 무게 차이도 같이 압축해야 한다.

 

아래와 같이 두 배열을 정의하자. 

group[i] := i 번 샘플이 속한 그룹 중 가장 무거운 샘플의 번호 ( union-find 시 최고 조상 역할도 같이 수행 )

dist[i] := i 번 샘플이 속한 그룹에서 가장 무거운 샘플의 무게 - i 번 샘플의 무게

 

그렇다면 서로 다른 두 그룹을 어떻게 합쳐주면 될까?

위 그림처럼 x, y 가 아직은 서로 다른 그룹에 속해 있다고 하자.

일반적인 문제라면, x 의 최고조상과 y 의 최고조상 중 아무거나 둘 중 하나의 조상이 되면 된다.

즉 (x 의 최고조상)->(y의 최고조상) 을 하던 (y의 최고조상) -> (x의 최고조상) 을 하던 상관이 없다.

 

하지만 이 문제는 한 그룹 내에서 가장 무거운 샘플이 최고 조상이 되게 설계했으므로,

x 의 최고조상, y 의 최고조상 중 더 무거운 것이 합친 그룹의 최고 조상이 되어야만 한다.

 

위 그림처럼, x 의 최고 조상을 X 라 하고, y 의 최고 조상을 Y 라고 하자.

파란색 화살표의 의미는 위에서 dist[i] 의 정의를 이해했으면 금방 알 수 있다.

그럼 우리는 X, Y 의 무게를 각각 알 수 있다.

 

X 의 무게 = x 의 무게 + dist[x]

Y 의 무게 = x 의 무게 + z + dist[y] 

 

따라서, dist[x] 와 z + dist[y] 의 대소관계만 안다면 X 와 Y 의 대소관계를 알 수 있다.

위 그림은 X 가 Y 보다 무거울 때 그래프의 변화다.

X 가 Y 보다 dist[x] - (z + dist[y])  만큼 무거우니까 Y -> X 로 간선을 연결해준다.

물론 group[Y] = X, dist[Y] = dist[x] - (z + dist[y]) 가 되는 것이다.

 

이런식으로 union 작업을 해주면 되고, find 시 경로 압축은 간단하다.

k 의 조상을 찾을 때, group[k] 의 조상 찾기를 먼저 하여 dist[group[k]] 를 정확히 구한다.

그 후, dist[k] += dist[group[k]] 를 해주면 k 에서 최고조상까지 직접 가지 않아도 dist 를 알 수 있다.

 

ll seek(ll k){
    if(k == group[k]) return k; /// 최고조상
    seek(group[k]); /// group[k] 의 최고조상을 먼저 구해준다
    dist[k] += dist[group[k]]; /// dist 갱신
    return group[k] = seek(group[k]); /// 경로 압축
}

 

find 의 대략적인 코드는 위와 같다.