[구름톤 챌린지] 16일차 - 연합 [Python]

goorm - 구름톤챌린지 16일차

goorm - 구름톤챌린지 16일차

---

풀이

N개의 섬에 대해 양방향으로 연결된 그룹의 개수를 구하는 문제다.

입력시에는 단방향으로만 입력받아야 한다.

1 ~ N 번 노드에 대해 방문하지 않은 노드에대해 bfs를 해주면 된다.

정점 u부터 시작해 연결 가능한 모든 정점을 확인하며, 양방향인 경우에만 방문표시와 함께 다음 탐색대상으로 포함시키면된다.

더 이상 탐색할 수 있는 정점이 없다면 bfs를 종료하며 1을 반환해 그룹의 개수를 증가시키면 된다.

---

출처

구름LEVEL