[BOJ] 1260번 : DFS와 BFS

1. 문제

1260번: DFS와 BFS

1. 여러 간선 정보를 통해 그래프가 주어진다.
2. 이때 DFS와 BFS 알고리즘을 통해 그래프를 탐색한다
3. 정점 번호가 작은 것을 우선 방문한다.

2. 알고리즘

• DFS
• BFS

3. 소스코드

from collections import defaultdict, deque

# n : 정점 개수, m : 간선 개수, v : 시작 정점
n, m, v = map(int, input().split())
graph = defaultdict(list) # defaultdict를 이용한 그래프

for _ in range(m):
	u, w = map(int, input().split()) # 정점 u와 w 연결
	graph[u].append(w)
	graph[w].append(u)

# 작은 정점부터 방문하기 위해서 오름차순 정렬
for i in graph:
	graph[i].sort()

visited = set() # 방문 여부 저장

# dfs 함수 정의
def dfs(v, visited):
	visited.add(v)
	print(v, end=' ')
	
	for i in graph[v]: # 인접 노드
		if i not in visited: # 방문하지 않은 경우 탐색
			dfs(i, visited)

# bfs 함수 정의
def bfs(v, visited):
	q = deque() # bfs를 위한 자료구조 queue 
	q.append(v)
	visited.add(v)
		
	# queue가 빌 때 까지
	while q:
		node = q.popleft()
		print(node, end=' ')
				
		# 인접노드 queue에 push
		for i in graph[node]:
			if i not in visited:
				visited.add(i)
				q.append(i)

dfs(v, visited)
visited.clear() # 방문 노드 초기화
print()
bfs(v, visited)

4. 주의

BFS 탐색을 위해서는 queue 자료구조가 필요하다. 이때 queue 자료구조를 위해서 세 가지 방법이 존재한다.

1. list

2. deque in collections

3. Queue in queue

4. list

파이썬 기본 자료구조인 list는 pop()함수를 통해서 원하는 인덱스의 요소를 꺼낼 수 있다. 그러나 pop(0) 같은 경우에 뒤에 인덱스들을 당기는 오버로드가 존재하기 때문에 O(n)이라는 시간복잡도를 가진다. bfs 같은 경우에 pop 연산을 여러 번 수행하기 때문에 가뜩이나 느린 파이썬을 더 느리게 만든다.

2. deque

deque에서 pop 연산은 popleft() 함수를 통해서 지원이 되는데 O(1)의 시간복잡도를 가진다. 따라서 queue 자료구조를 사용한다면 deque를 사용하는 것이 가장 적합하다

3. Queue

queue 모듈의 Queue는 멀티쓰레드를 지원하기 위해서 사용되는 자료구조이다. 따라서 연산 과정에서 locking 연산과 같은 불필요한 연산이 추가로 사용되기 때문에 deque에 비해서 느리다.

따라서 종합적으로 볼 때, 코딩테스트에서는 queue 자료구조를 위해서 deque를 사용하는 것이 가장 적합하다.