[BOJ] 1260번 DFS와 BFS

[BOJ] 1260번 DFS와 BFS 문제

기초적인 DFS와 BFS를 알아보는 그래프 문제다.

그래프는 코딩 뉴비 절단기 삼대장 중 하나일 정도로 매우 어렵다

문제에 들어가기 앞서 DFS와 BFS를 간략히 짚어보자.

---

DFS는 Depth First Search, BFS는 Breadth First Search로 각각 깊이 우선 탐색, 너비 우선 탐색이다.

이 문제를 풀기 위해서는 노드 간의 관계와 시작하는 정점이 필요하다.

또한 DFS와 BFS는 각각 재귀와 데크(Deque)로 푸는 것이 일반적이라고 알려져 있다.

하지만 DFS를 재귀로 푸는 게 쉽긴 하지만 파이썬은 최대 재귀 한도 에러가 존재해서 위험할 수 있다.

그래서 데크로 DFS를 푸는 방법이 존재하기 때문에 이를 사용해서 공부했다.

---

DFS는 깊이를 우선해서 탐색하는데, 말 그대로 노드를 끝까지 파내는 알고리즘이다.

BFS는 너비를 우선해서 탐색하며, 한 노드의 모든 연결된 노드를 확인하고 이를 반복하는 알고리즘이다.

두 알고리즘의 차이는 꽤나 명백해서 쓰이는 곳이 다르다.

DFS와 BFS를 쉽게 이해할 수 있는 움짤

---

import sys
from collections import deque

def dfs(n, v) -> list:
	dfs_visited = [False for _ in range(n+1)]
	dfs_travel = deque([v])
	dfs_ans = list()

	while dfs_travel:
		now_node = dfs_travel.popleft()
		if not dfs_visited[now_node]:
			dfs_ans.append(now_node)
		dfs_visited[now_node] = True
		for next_node in nodes[now_node][::-1]:
			if not dfs_visited[next_node]:
				dfs_travel.appendleft(next_node)

	return dfs_ans

def bfs(n, v) -> list:
	bfs_visited = [False for _ in range(n+1)]
	bfs_travel = deque([v])
	bfs_ans = list()

	while bfs_travel:
		now_node = bfs_travel.popleft()
		if not bfs_visited[now_node]:
			bfs_ans.append(now_node)
		bfs_visited[now_node] = True
		for next_node in nodes[now_node]:
			if not bfs_visited[next_node]:
				bfs_travel.append(next_node)

	return bfs_ans

if __name__ == '__main__':
	N, M, V = map(int, sys.stdin.readline().rstrip().split())
	nodes = [[] for _ in range(N+1)]
	for _ in range(M):
		n_s, n_e = map(int, sys.stdin.readline().rstrip().split())
		nodes[n_s].append(n_e)
		nodes[n_e].append(n_s)

	for now_node in nodes:
		now_node.sort()

	print(*dfs(N, V))
	print(*bfs(N, V))

 

nodes의 크기를 N+1로 한 이유는 입력받은 숫자에 1을 빼지 않고 그대로 써먹기 위함이다.

이 부분은 개인 차이긴 하지만 난 이 방법을 굉장히 선호한다. -1 붙는 게 꽤 거슬리기 때문이다.

dfs 함수의 경우, 스택이 아닌 데크로 풀기 위해선 기존에 정렬된 노드 순서의 역순으로 appendleft를 해야 한다.