[Python] BFS(너비 우선 탐색), DFS(깊이 우선 탐색)

백준 1260문제

BFS

데크 활용, 양쪽으로 가능 

데크 : root에서 출발 -> 제일 왼쪽거 꺼냄(n) -> n이 첫 방문이면 추가(visited) -> n연결된 노드 추가(queue)

데크: [3]에서 출발 -> 3꺼냄 -> 3추가 -> 데크에 [1, 4] 추가

데크: [1, 4] 출발 -> 1꺼냄 -> 1추가 -> 데크에 [2, 3] 추가

데크: [4, 2, 3] 출발 -> 4꺼냄 -> 4추가 -> 데크에 [3, 5] 추가

데크: [2, 3, 3, 5] 출발 -> 2꺼냄 -> 2추가 -> 데크에 [1, 5] 추가

데크: [3, 3, 5, 1, 5] 출발 -> 3꺼냄 -> 3안추가(visited에 있음) -> 아무것도 안함

데크: [3, 5, 1, 5] 출발 -> 3꺼냄 -> 3안추가(visited에 있음) -> 아무것도 안함

데크: [5, 1, 5] 출발 -> 5꺼냄 -> 5추가 -> 데크에 [2, 4] 추가

데크: [1, 5, 2, 4]출발 여기까지 할게요,,

def bfs(graph, root):
    visited = []
    queue = collections.deque([root])

    while queue:
        n = queue.popleft()
        if n not in visited:
            visited.append(n)
            if n in graph:
                queue.extend(graph[n])
    return visited

DFS

스택 활용, 맨 오른쪽 거

스택: root에서 출발 -> 제일 오른쪽거 꺼냄(n) -> n이 첫 방문이면 추가(visited) -> n연결된 노드 추가(stack)

스택: [3]에서 출발 -> 3꺼냄 -> 3추가 -> 스택에 [4, 1] 추가 (작은 수부터 돌기 위해 reversed)

스택: [4, 1] 출발 -> 1꺼냄 -> 1추가 -> 스택에 [3, 2] 추가 (reversed)

스택: [4, 3, 2] 출발 -> 2꺼냄 -> 2추가 -> 스택에 [5, 1] 추가 (reversed)

스택: [4, 3, 5, 1] 출발 -> 1꺼냄 -> 1안추가(visited에 있음) -> 아무것도 안함

스택: [4, 3, 5] 출발 -> 5꺼냄 -> 5추가 -> 스택에 [4, 2] 추가 (reversed)

스택: [4, 3, 4, 2] 출발 -> 2꺼냄 -> 2안추가(visited에 있음) -> 아무것도 안함

스택: [4, 3, 4] 출발 -> 4꺼냄 -> 4추가 -> 스택에 [5, 3] 추가 (reversed)

스택: [4, 3, 5, 3] 출발 여기까지 할게여,,

def dfs(graph, root):
    visited = []
    stack = [root]

    while stack:
        n = stack.pop()
        if n not in visited:
            visited.append(n)
            if n in graph:
                stack.extend(reversed(graph[n]))
    return visited

 

전체 코드

from collections import deque
import collections

N,M,V = map(int,input().split())

graph = collections.defaultdict(list)
for i in range(M):
    a, b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)
    graph[a].sort()
    graph[b].sort()

def bfs(graph, root):
    visited = []
    queue = collections.deque([root])

    while queue:
        n = queue.popleft()
        if n not in visited:
            visited.append(n)
            if n in graph:
                queue.extend(graph[n])
    return visited

def dfs(graph, root):
    visited = []
    stack = [root]

    while stack:
        n = stack.pop()
        if n not in visited:
            visited.append(n)
            if n in graph:
                stack.extend(reversed(graph[n]))
    return visited

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