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

구름톤 챌린지 17일차입니다. 4주차가 시작되면서 점점 구름톤 챌린지도 마무리되어가고 있습니다. 챌린지를 통해 문제 풀이 실력을 향상시킬 수 있으며, 블로그에 학습 일기도 작성하면 추가 보상도 주어지니 관심 있으시면 참여해보시는 것을 추천드립니다.

https://level.goorm.io/l/challenge/goormthon-challenge

구름LEVEL

 

문제

입력 / 출력

풀이 과정

BFS를 통해 컴포넌트 그룹을 탐색했다. 한 컴포넌트를 탐색하면서 간선의 개수도 동시에 세주어 저장하였다.

이를 이용해 가장 밀도가 높고, 컴포넌트를 구성하는 컴퓨터의 수가 가장 적고, 더 작은 번호를 가진 컴퓨터가 있는 컴포넌트 순대로 정렬하여 조건을 만족하는 컴포넌트를 출력했다.

import sys
from collections import deque
input = sys.stdin.readline

n, m = map(int, input().rstrip().split())
graph = [{} for _ in range(n+1)]
for _ in range(m):
	a, b = map(int, input().rstrip().split())
	graph[a][b] = 1
	graph[b][a] = 1

visited = [0 for _ in range(n+1)]
component = []
for i in range(1, n+1):
	if visited[i] == 0:
		# 통신 회선 개수 / 컴퓨터 목록
		cnt = 0
		computer_list = [i]
		
		queue = deque()
		queue.append(i)
		
		visited[i] = 1
		
		while queue:
			now = queue.popleft()
			
			graph_keys = list(graph[now].keys())
			for k in graph_keys:
				if visited[k] == 0:
					visited[k] = 1
					
					cnt += 1
					del graph[now][k]
					del graph[k][now]
					
					queue.append(k)
					computer_list.append(k)
				else:
					cnt += 1
					del graph[now][k]
					del graph[k][now]
		
		component.append([cnt, list(sorted(computer_list))])

component.sort(key=lambda x:(-(x[0]/len(x[1])), len(x[1]), x[1][0]))
print(' '.join(map(str, component[0][1])))