[구름톤 챌린지] Day 17 - 통신망 분석(DFS/BFS)

https://level.goorm.io/exam/195699/%EA%B7%B8%EB%9E%98%ED%94%84%EC%9D%98-%EB%B0%80%EC%A7%91%EB%8F%84/quiz/1

구름LEVEL

해당 문제는 그래프의 컴포넌트 개념과 다중 조건 정렬을 활용한 해결이 필요하다

---

문제

---

풀이

from collections import deque

n,m = map(int,input().split())

graph = [[] for _ in range(n+1)]

visited = [0]*(n+1)


# 양방향으로 그래프 만들기
for _ in range(m):
	a,b = map(int,input().split())
	graph[a].append(b)
	graph[b].append(a)
	

# 나중에 다중 조건에 맞춰서 정렬하는 함수
def condition(arrs):
	# 조건1, 조건 2, 조건 3에 맞춰서 오름차순 정렬/ 이때, 2개는 최소값인데 1개는 최댓값일 경우 역순으로 만들기
	res = sorted(arrs, key= lambda x : (len(x[0])/x[1], len(x[0]) , min(x[0])))
	return res

dq = deque()
answer = []

for i in range(1,n+1):
	# 방문했거나 연결된 노드가 없으면 건너띄기
	if visited[i] or not graph[i]:
		continue
	
	# 첫방문일때 dq에 넣기
	dq.append(i)
	# 방문처리
	visited[i] = 1
	#연결된 노드 넣을 리스트
	cluster = []
	#연결된 통신 노드 갯수 -> 나중에 //2 필요
	cnt = 0
	
	while dq:
		now = dq.popleft()
		## 연결된 통신 노드 숫자 세기

		cnt += len(graph[now])
		# 첫 시작 컴포넌트와 연결된 것 모두 넣기
		cluster.append(now)
		for to in graph[now]:
			if not visited[to] :
				dq.append(to)
				visited[to] = 1
				
	answer.append((cluster,cnt//2))

answer = condition(answer)
answer = sorted(answer[0][0])

for i in answer:
	print(i,end = " ")

1. 해당 그래프와 연결된 노드 갯수세고 //2를 하여 몇개가 연결되어있는지 확인

2. 다중조건에 맞춰서 정렬

3. sorted를 통해 정렬할때, 2개의 조건은 오름순, 1개의 조건은 내림순이라면 1개의 조건에 (-) 부호를 붙여 오름순으로 바꿔주면 된다.