[Python] BFS/DFS 구현 기본 코드 & 기초 문제

DFS / BFS 구현 예제

일반적인 경우 실제 수행 시간은 BFS가 DFS보다 좋은 편이다.

DFS

def dfs(graph, v, visited):
	# 현재 노드를 방문 처리
    visited[v] = True
    print(v, end=' ')	# 노드의 탐색 순서 출력
    # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v]:
    	if not visited[i]:
            dfs(graph, i, visited)
    
# 그래프를 2차원 인접 리스트 방식으로 표현함
graph = [
	[],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

visited = [False] * 9

dfs(graph, 1, visited)

동작 원리 : 스택

구현 방법 : 재귀 함수 이용

 

BFS

from collections import deque

def bfs(graph, start, visited):
    queue = deque([start])	# argument가 '[start]'임을 주의
   	visited[start] = True
    
    while queue:
    	v = queue.popleft()
        print(v, end = ' ')	# 노드의 탐색 순서 출력
        
    	for i in graph[v]:
        	if not visited[i]:
        		queue.append(i)
            	visited[i] = True
 
 # 그래프를 2차원 인접 리스트 방식으로 표현함
graph = [
	[],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

visited = [False] * 9

bfs(graph, 1, visited)

👉 코드 상의 4번째 줄 부가 설명
    deque는 문자열, 튜플, 리스트 등 iterable 객체를 받아서 덱을 초기화한다.
    만약 deque(start)를 넣고 start가 1이라면 deque(1)은 에러를 발생시킨다.
    하지만 만약 start가 'abc'와 같은 문자열이라면 문자열의 각 문자를 요소로 처리한다.
    어쨌든 위 코드에서 deque([start])는 start 값을 리스트로 감싸서 하나의 요소로 덱에 넣어 초기화한다.

 

동작 원리 : 큐

구현 방법 : 큐 자료구조 이용

문제

🥈  백준 1260. DFS와 BFS

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

from collections import deque

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

graph = [[] for _ in range(n+1)]
for i in range(m):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)
        
for i in range(1, n+1):
    graph[i] = sorted(graph[i])

def dfs(v, visited, graph):
    visited[v] = True
    print(v, end=' ')
    for node in graph[v]:
        if not visited[node]:
            dfs(node, visited, graph)

def bfs(v, visited, graph):
    queue = deque([v])
    visited[v] = True
    while queue:
        node = queue.popleft()
        print(node, end=' ')
        for item in graph[node]:
            if not visited[item]:
                queue.append(item)
                visited[item] = True

visited = [False] * (n+1)
dfs(v, visited, graph)
print()

visited = [False] * (n+1)
bfs(v, visited, graph)