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

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

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

구름LEVEL

 

문제

입력 / 출력

풀이 과정

BFS를 이용해 탐색한다. s번 섬에서 e번 섬으로 가는 다리가 있을 때 e번 섬에서 s번 섬으로 가는 다리가 있다면 같은 연합으로 인식하고 탐색한다. 이를 이용해 연합의 개수를 세면 되는 문제이다.

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):
	s, e = map(int, input().rstrip().split())
	graph[s].append(e)

visited = [0 for _ in range(n+1)]
result = 0
	
for i in range(1, n+1):
	if visited[i] == 0:
		visited[i] = 1
		result += 1
		
		queue = deque()
		queue.append(i)
		
		while queue:
			now = queue.popleft()
			
			for next_node in graph[now]:
				if visited[next_node] == 0 and now in graph[next_node]:
					visited[next_node] = 1
					queue.append(next_node)

print(result)