[구름톤 챌린지] Day 16 - 연합(그래프 탐색)

https://level.goorm.io/exam/195698/%EC%97%B0%ED%95%A9/quiz/1

구름LEVEL

해당 문제는 그래프에서 컴포넌트의 개수를 찾는 문제입니다. 컴포넌트와 그래프 탐색 개념이 필요합니다.

---

문제

 

---

풀이

from collections import deque

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

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

visited = [0]*(n+1)

dq = deque()

for _ in range(m):
	a,b = map(int,input().split())
	graph[a].append(b)
	
result = 0

for i in range(1,n+1):
	# 방문했다면 건너띄기
	if visited[i]:
		continue
		
	dq.append(i)
	result += 1
	visited[i] = 1
	
	while dq:
		now = dq.popleft()
		for to in graph[now]:
			if not visited[to] and now in graph[to]:
				dq.append(to)
				visited[to] = 1
	
print(result)

1. 단방향이기때문에 grahp[a].append(b)만 적용

2. 방문했는지 안했는지 확인하고 방문안했으면 그래프의 인덱스에 담긴 애들을 bfs로 탐색

3. popleft()하면 BFS, pop()하면 DFS로 접근하는 것을 알아야함