구름톤 챌린지 4주 차 학습 일기(Day 01)

문제

이 세상에는 수많은 컴퓨터들이 통신망을 통해 서로 연결되어 정보를 교류하고 있다. 오늘 플레이어는 이 거대한 통신망 중 한 구역을 조사하고자 한다.

플레이어가 조사할 구역에는 N개의 컴퓨터가 있고, M개의 통신 회선이 있다. 각 컴퓨터는 1번부터 N번까지 번호가 붙어 있고, 통신 회선은 서로 다른 두 컴퓨터를 양방향으로 연결하고 있다.

컴퓨터들은 연결 여부에 따라 여러 개의 컴포넌트로 나뉜다. 어떤 두 컴퓨터가 통신 회선만을 이용해서 연결되어 있다면 두 컴퓨터는 같은 컴포넌트에 속한다.

플레이어는 여러 개의 컴포넌트 중, 가장 밀도가 높은 컴포넌트를 조사하려고 한다. 컴포넌트의 밀도는 그 컴포넌트에 포함된 통신 회선의 개수를 컴퓨터의 수로 나눈 값이다. 주어진 통신 구역을 분석해서, 가장 밀도가 높은 컴포넌트의 정보를 출력해보자.

 

 

 

예제 설명

첫 번째 예제에서 주어진 통신 구역에는 두 개의 컴포넌트가 있다. 한 컴포넌트는 (1, 3, 5, 7)번 컴퓨터로 이루어져 있고, 다른 컴포넌트는 (2, 4, 6)번 컴포넌트로 이루어져 있다.

(1, 3, 5, 7)번 정점으로 구성된 컴포넌트에는 네 개의 통신 회선이 존재하므로, 이 컴포넌트의 밀도는 4/4 = 1이다. (2, 4, 6)번 컴퓨터로 구성된 컴포넌트에는 두 개의 통신 회선이 존재하므로, 이 컴포넌트의 밀도는 2/3이다. 먼저 주어진 컴포넌트의 밀도가 더 크므로, 1 3 5 7을 답으로 출력해야 한다.

 

 

코드

from collections import deque
from sys import stdin as s

N,M = map(int,s.readline().split())
graph = [[] for _ in range(N+1)]
ans = [[] for _ in range(N+1)]
answer = []
v = [0]*(N+1)

for _ in range(M):
	a,b = map(int,s.readline().split())
	graph[a].append(b)
	graph[b].append(a)
	
for i in range(1,N+1):
	if v[i]:
		continue
	
	q = deque([i])
	v[i] = 1
	ans[i].append(i)
	result=0
	
	while q:
		now = q.popleft()
		
		for to in graph[now]:
			if now in graph[to]:
				result+=1
				if not v[to]: 
					ans[i].append(to)
					q.append(to)
					v[to]=1
	ans[i].append(result//2)
density = 0

for an in ans:
    if an:
        dens = an[-1] / (len(an)-1)
        if dens > density:
            answer = an[:(len(an)-1)]
            density = dens
print(*sorted(answer))

 

 

 

느낀점

우선 이 문제를 봤을 때는 구름톤 16일차 문제와 비슷한 느낌의 BFS라는걸 느꼈습니다. 하지만 원래 처음에 짯던 코드에서는 조건문을

 

while q:
    now = q.popleft()

    for to in graph[now]:
        if not v[to] and now in graph[to]: 
        result+=1
        ans[i].append(to)
        q.append(to)
v[to]=1
	ans[i].append(result)

 

위와 같은 코드로 작성을해서 예제 1번의 경우 이미 컴포넌트가 4개의 통신으로 이루어져야하는데 이미 방문처리가 되어있어서 갯수를 세는데 문제가 생겼습니다. 그래서 정답코드처럼 코드를 바꾼후에 밀도를 비교해서 높은 밀도를 가진 배열을 출력하도록 했습니다.

BFS는 방문처리를 어떻게 하냐에따라서 문제가 달라지는걸 느꼈습니다.