2606 바이러스

2606. 바이러스 / c++ / Silver3 / 20분

문제 및 코드

접근 방식

Union Find

1. 연결된 컴퓨터 쌍 A, B가 주어질 때 A와 B의 Root를 구한다. (여기선 Parent)
2. 두 Parent 가 같다면 이미 같은 그래프에 속해 있으므로 패스
3. 두 Parent 가 다르다면 한쪽의 Parent를 다른 한쪽의 Parent 로 연결지어 준다.
   (ex. Parent[ParentA] = ParentB)
4. 연결이 다 끝난 후 Parent가 1인 정점의 갯수를 리턴
5. 그런데 Union (연결) 과정에서 추가 조건이 필요했다. 난 1번 정점과 연결되어 있는지를 판별하기 위해 Parent[i] == 1 을 만족시켜야 했으므로, ParentA 와 ParentB의 값 중 작은 값이 최종 부모가 되도록 체크해줘야 했다.

다시 생각해 볼 점

1. Union-Find, DFS, BFS, 등 그래프 탐색 알고리즘으로 풀 수 있는 문제였다. 그중 Union-Find 알고리즘을 선택했는데, Union(연결) 부분에서 조건을 명확히 해줘야 한다는 점을 다시금 깨달았다.
2. 마지막에 부모를 체크할 때 그냥 if(Parent[i] == 1) 해버리면 문제가 생길 수 있어서 (아마 5번의 부모값 비교를 안해줬을 때에만 발생했을 것 같긴하지만) if (GetParent(i) == 1) 로 체크해줘야 했다.