백준 13306 자바 - 트리 (BOJ 13306 JAVA)

[ 백준 13306 ]

[ 코드 (깃헙) ]

 

 

  트리의 부모를 알려주고, 주어진 쿼리를 해결하는 문제이다. 쿼리는 '0 b'와 같이 들어오면 b번째 edge 제거하는 쿼리와, '1 c d'와 같이 들어오면 c와 d 사이에 연결경로가 있는지 묻는 쿼리가 있다.

 

  일단 거리 자체를 묻지 않고, 연결 경로가 있는지만 파악하면 된다. 그럼 이거엔 union-find 알고리즘을 쓰면 될 것임을 알 수 있다. 다만 해당 알고리즘의 경우 그룹간의 관계를 맺는것은 쉽지만, 연결을 끊는건 힘들다. 그럼 쿼리를 반대순서로 보면 어떻게 될까? 원래 순서대로라면 '간선들이 존재하는 그래프에서 edge를 제거하면서 중간중간 특정 노드간에 연결경로가 있는지 묻는 쿼리' 이지만, 반대로 미리 쿼리상에 존재하는 모든 간선을 제거한 후 역순으로 보면 '간선을 연결하면서 중간중간 특정 노드간에 연결경로가 있는지 묻는 쿼리'가 된다. 그럼 union-find만 알고있다면 매우 쉬운 문제가 된다. 

 

로직을 정리하면 다음과 같다.

 

A. 쿼리에 존재하는 간선을 미리 제거한다. 정확히는 쿼리에 없는 간선만 연결해두면 된다. 다만 이 문제의 경우 'N-1개는 (1)의 형태'라는 조건이 있고, 트리는 항상 N-1개의 간선을 가지므로 단순히 간선을 아무것도 연결하지 않은채로 시작하면 된다.

 

B. union-find를 사용해 쿼리를 역순으로 진행하면서 출력할 내용을 어딘가에 역순으로 쌓아둔다. (당연히 답은 역순으로 출력하면 안된다)

 

C. 쌓아둔 답변을 원래 출력해야할 순서대로 출력한다.