[Algorithm] BFS/DFS

BFS, DFS는 그래프 탐색 알고리즘으로 각각 너비우선탐색, 깊이우선 탐색이다. 두 알고리즘 문제를 풀 때는 아래 2가지를 생각하면 도움이 된다.

1. 방문한 노드 리스트와 방문할 노드 리스트가 필요하다.
2. 방문할 노드 리스트를 BFS는 queue로, DFS는 stack으로 구현한다.

파이썬 코드

from collections import deque

# graph = {k: [] for k in range(N)}
graph = {
'A': ['B', 'C'],
'B': ['D'],
'C': ['G', 'H', 'I'],
'D': ['E', 'F'],
'E': ['D'],
'F': ['D'],
'G': ['C'],
'H': ['C'],
'I': ['C', 'J'],
'J': ['I']
}
root_node = 'A'

def bfs(graph, root):
visited = []
need_visit = deque([root])
    while need_visit:
        node = need_visit.popleft()
        if node not in visited:
            visited.append(node)
            need_visit += graph[node]
    return visited

def dfs(graph, root):
visited = []
need_visit = []
    need_visit.append(root)
    while need_visit:
        node = need_visit.pop()
        if node not in visited:
            visited.append(node)
            need_visit += graph[node]
    return visited

코틀린 코드

추천 문제

https://www.acmicpc.net/problem/1260 https://www.acmicpc.net/problem/1697