백준 1260번: DFS와 BFS (Python)

접근

DFS는 깊이 우선 탐색, BFS는 너비 위주 탐색이다.

DFS는 첫번째 이웃으로 이동하고나서, 해당 이웃을 기준삼아 다시 또 첫번째 이웃으로 이동하고 동일하게 계속 진행하여 더이상 연결이 되지 않을 때까지 진행하고 돌아와 두번째 이웃으로 진행한다.

BFS는 첫번째 기점에서 연결된 모든 이웃을 탐색한 후에, 첫번째 이웃에서 같은 작업을 반복한다.

코드

import sys

n, m, start = map(int, sys.stdin.readline().split())
lines = [[0 for _ in range(n + 1)] for __ in range(n + 1)]
for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())
    lines[a][b] = lines[b][a] = 1
dfsvisited = [0 for _ in range(n + 1)]
bfsvisited = [0 for _ in range(n + 1)]
dfslist = []
bfslist = []


def dfs(x):
    dfsvisited[x] = 1
    dfslist.append(x)
    for i in range(1, n + 1):
        if dfsvisited[i] == 0 and lines[x][i] == 1:
            dfs(i)


def bfs(x):
    q = [x]
    bfsvisited[x] = 1
    while q:
        x = q.pop(0)
        bfslist.append(x)
        for i in range(1, n + 1):
            if bfsvisited[i] == 0 and lines[x][i] == 1:
                q.append(i)
                bfsvisited[i] = 1


dfs(start)
bfs(start)
print(*dfslist)
print(*bfslist)

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!