[구름톤 챌린지] 17일차 - 통신망 분석

goorm - 구름톤챌린지 17일차

goorm - 구름톤챌린지 17일차

---

풀이

N개의 정점에 대해 컴포넌트의 밀도가 높은, 하나로 연결된 정점을 간선으로 나눈 수치가 최대인 컴퓨터들의 목록을 출력해주면 되는 문제다.

 

연결만 되어있다면 동일한 컴포넌트로 볼 수 있으니 양방향그래프로 초기설정을 해주자.

이제 모든 정점에 대해 하나의 컴포넌트에 속하는 컴퓨터들의 목록을 저장해 반환해주는 bfs를 실행하자.

방문하지 않은 정점들에 대해 연결된 모든 정점을 set인 path에 추가해주는 방법으로 중복을 제거했다.

하나의 컴포넌트에 속한 컴퓨터를 모두 찾았다면, 해당 컴퓨터와 연결된 컴퓨터가 컴포넌트에 존재하는 만큼 간선의 개수를 계산하자.

반환받은 컴포넌트 내 컴퓨터 목록과 밀도를 이용해 문제에서 주어진 조건대로 알맞는 컴포넌트로 갱신 후

 탐색이 모두 종료되었을 때 조건에 부합하는 컴포넌트 내 컴퓨터 목록을 출력해주면 된다.

---

출처

구름LEVEL