dfs, bfs

링크텍스트

예제 1 백준 알고리즘 1260 풀이

from sys import stdin
read = stdin.readline

N, M, V = map(int, read().split())
graph = [[0]*(N+1) for _ in range(N+1)]
visited = [False]*(N+1)

#그래프 각 리스트에 연결된 부분 1로
for _ in range(M):
    x, y = map(int, read().split())
    graph[x][y] = 1
    graph[y][x] = 1

#재귀함수 호출하여 연결된 인자로 깊이 탐색
def dfs(V):
    visited[V] = True
    print(V, end=' ')
    for i in range(1, N+1):
        if not visited[i] and graph[V][i] == 1:
            dfs(i)
         
#que에 1개씩 인자를 넣어 근접 탐색
def bfs(V):
    visited[V] = False
    queue = [V]
    while queue:
        V = queue.pop(0)
        print(V, end=' ')
        for i in range(1, N+1):
            if visited[i] and graph[V][i] == 1:
                queue.append(i)
                visited[i] = False
dfs(V)
print() #dfs, bfs 다른 줄에 출력하기 위해
bfs(V)

DFS 깊이 우선 탐색

graph = [
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]


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

visited = [False]*9
dfs(graph, 4, visited)

bfs
간선 길이 동일 최단거리 구할 떄 사용

from collections import deque