dfs bfs

문제로 보는 정리

1260번: DFS와 BFS

1. BFS & DFS 설계 (인접 리스트)

from collections import deque

n, m, v = map(int, input().split(" "))
visit = [False] * (n + 1)
arr = [[] for i in range(n + 1)]
for i in range(m):
    a, b = map(int, input().split(" "))
    arr[a].append(b)
    arr[b].append(a)


def dfs(start):
    print(start, end=" ")
    visit[start] = True
    for a in arr[start]:
        if not visit[a]:
            dfs(a)


def bfs(start):
    queue = deque([start])
    visit[start] = True
    while queue:
        q = queue.popleft()
        print(q, end=" ")
        for a in arr[q]:
            if not visit[a]:
                queue.append(a)
                visit[a] = True


for i in range(1, n + 1): arr[i].sort()

dfs(v)
visit = [False] * (n + 1)
print()
bfs(v)

2. BFS & DFS 설계 (배열)

from collections import deque

n, m, v = map(int, input().split(" "))
arr = [[0] * (n + 1) for i in range(n + 1)]
visit = [False] * (n + 1)
for i in range(m):
    x, y = map(int, input().split())
    arr[x][y] = 1
    arr[y][x] = 1


def dfs(start):
    print(start, end=" ")
    visit[start] = True
    for i in range(1, n + 1):
        if not visit[i] and arr[start][i] == 1:
            dfs(i)


def bfs(start):
    queue = deque([start])
    visit[start] = True
    while queue:
        q = queue.popleft()
        print(q, end=" ")
        for i in range(1, n + 1):
            if not visit[i] and arr[q][i] == 1:
                queue.append(i)
                visit[i] = True


dfs(v)
print()
visit = [False] * (n + 1)
bfs(v)