[백준] No.13306 - 트리 (C++, 오프라인 알고리즘)

문제

 

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

13306번: 트리

 

 

풀이

 

solved.ac 난이도: Platium 5

 

 

해당 문제에서 오프라인 알고리즘으로 해결해도 된다는 것을 알아차리는 게 중요했다.

 

온라인 알고리즘은  대부분의 문제들에서 원하는 출력 방식으로,

입력으로 답을 할 쿼리(질의)가 주어지면 바로 다음 줄에 답을 출력해주어야 한다.

온라인 알고리즘에서는 모든 입력 데이터를 가지지 않은 상태에서의 실시간 입출력이 중요하다.

 

오프라인 알고리즘은 데이터를 모두 입력받은 후 질의의 답을 한다.

따라서 쿼리마다 답을 출력해줄 필요 없이 모든 데이터를 입력받고 후에 답을 해도 된다.

 

문제에서 오프라인 알고리즘에 대한 힌트는 출력 설명문에 있었다.

 

표준 출력으로 질의에 대한 답을 순서대로 Q개의 줄에 출력한다. 

 

만약 해당 문제를 온라인으로 (질의마다 답을 바로 출력 시) 해결한다면

일단 입력받은 부모를 토대로 Union-Find 자료구조의 부모 관계를 구성한다.

(Union-Find 자료구조, 분리 집합에 대해서는 아래의 게시글 참조)

유니온-파인드(Union-Find), 분리 집합

 

그 후, (1) 타입의 입력이 주어지면 b의 부모를 자기 자신으로 바꾸어 집합을 분리시켜 준다.

(Union-Find 자료구조에서 집합의 루트는 자기 자신을 부모로 가리키므로)

 

아래와 같은 트리(집합) 구조에서 b=3 정점과 부모의 에지를 끊으면

 

상태 1

 

 

두 개의 집합으로 분리된다.

상태 2

 

(1) 타입의 입력에서는 이렇게 집합을 분리시켜주고

(2) 타입의 입력에서는 Find( )함수를 통해 두 정점의 루트가 같은지 확인하면 된다.

 

하지만 이러한 구현에서는 Find() 함수에서의 경로 압축(path compression) 최적화를 진행할 수 없다.

그 이유는,  경로 압축으로

return parent[u] = Find(parent[u]); 을 반환하면

위의 상태 1에서 Find(5)를 호출할 경우 parent[5] = 1로 경로 압축이 되어 저장된다.

이 상태에서 3의 부모 엣지와 연결이 끊겨 상태 2가 된다면 5는 집합의 루트인 3을 parent로 저장해야 하지만 이미 5로 업데이트된 상태이다.

 

따라서 어느 에지가 끊어 저도 집합의 루트로 올라갈 수 있도록 아래와 같이 한 단계씩 부모 노드로 올라가야 한다.

 

int Find(int u){
  if(parent[u] == u)
    return u;
  return Find(parent[u]);
}

 

하지만 위의 경로 압축 설명 게시글에서도 알 수 있듯이 편향 트리(한쪽으로 기울어진 트리)가 발생할 경우 집합의 루트로 올라가는 데 너무나 큰 시간이 소요된다.

 

이러한 이유로 온라인 알고리즘으로 해결 시 시간 초과가 발생한다.

 

 

 

이번에는 오프라인 알고리즘으로 해결해보자.

 

문제를 잘 읽어보면 다음과 같은 사실을 알 수 있다.

(1)의 형태(부모와의 엣지를 끊는 입력)는 N-1개가 주어진다.

즉, 모든 엣지(간선)의 수만큼의 입력이 주어지고 해당 입력에는 중복이 없다.

따라서 입력이 모두 끝난 최종적인 상태에서는 모든 노드들이 서로 연결이 끊어진 상태로 종료된다.

 

그렇다면 (1)형태의 입력을 역순으로 진행한다고 가정해보자.

원래 순서대로 진행시 (1)형태는 부모와 연결을 끊었으므로 역순에서는 반대로 b 노드와 부모 노드를 연결 해주게 된다.

ex) 상태1 -> 상태2는 부모와의 연결 해제, 반대로 상태2 -> 상태1는 부모와 연결!

 

노드가 이제 집합을 해제하는 과정이 아닌 새로운 집합으로 연결되는 과정을 거치게 된다.

이러한 과정의 장점이 바로 경로 압축 최적화를 진행할 수 있다는 것이다!

 

경로 압축 최적화로 구현한 Find로 진행한다고 생각해보자.

상태 2에서 5 노드는 루트인 3을 부모로 저장하고 있다. parent[5] =3;

이때 3 노드가 1 노드를 부모로 가지게 되면(연결 되면) parent[3] =1이되고

이 상태에서 Find(5)를 진행하여도 정상적으로 자신의 부모 3노드를 거쳐 루트 1에 도달할 수 있다.

 

단, (2)타입의 질의에서는 질의된 시점에서의 트리 노드들의 연결 여부를 확인하므로

입력 모두 받으면서 입력의 순서를 저장하고(오프라인 알고리즘)

입력의 역순으로, (1)타입의 입력은 부모와 연결하며 (2)타입의 입력은 연결 여부를 확인 후 출력을 위해 따로 저장해 주자.

 

입력을 저장하기 위해 본인은 pair<int,int>를 사용하여

vector<pair<int,int>> queries(query_num)

(1)타입의 입력에는 pair의 first에 0을, second에는 b 노드의 번호

(2)타입의 입력에는 first에 c, second에 d를 저장하여 first로 어떤 쿼리인지를 구분할 수 있게 하였다.

(노드들은 1 이상의 번호를 가지므로 first가 0이 아니면 모두 (2) 형태이다.)

 

 

 

 

코드