백준 14868

14868번: 문명

 

  백조의 호수랑 비슷한 문제. 옛날에 백조의 호수 풀 땐 유니온 파인드를 몰라서 서로 이어졌는지 확인하는 과정을 까다롭게 구현했었는데, 유니온 파인드를 알고 나니 체감 난이도가 확 떨어짐. 서로 다른 문명을 합치는 과정과 문명이 없는 곳에 문명을 전파하는 과정을 따로 구현하면 된다.

 

  먼저 문명을 합치는 큐를 돌리고 그 과정에 사용된 큐를 다시 전파용 큐로 전달해주고 문명 전파 후 새로 추가된 큐를 문명을 합치기 용 큐로 보내는 과정을 반복하면 된다. 문명을 합치는 연산이 모든 문명의 수 - 1번 행해지면 모든 문명이 합쳐진 걸 확인할 수 있다. 라이 블로그는 트리 사이즈랑 방문한 사이즈를 비교해서 판단한다는데, 그건 어떻게 구현한 건지 잘 모르겠다. 

 

 

 - Source code link

github.com/Bibidi/Algorithms/blob/master/boj/boj%2014868.cpp