greentea31's Note

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

풀이 과정

정점 수, 간선 수, 시작 점을 입력 받고 DFS, BFS를 사용했을 때의 순회 순서를 반환해주면 된다.

그래프의 간선을 파이썬의 딕셔너리를 활용하여 인접 리스트로 표현하고, DFS와 BFS를 통해 순회하였다. 방문할 수 있는 정점이 여러가지 인 경우 정점 번호가 작은 것을 먼저 방문하게 하려면 입력받은 인접 리스트를 정렬해주어야 한다.

소스 코드

from collections import deque
import sys

N, M, V = map(int, sys.stdin.readline().split())
g = {}
for i in range(N+1):
    g[i] = []
for _ in range(M):
    a, b = map(int, sys.stdin.readline().split())
    g[a].append(b)
    g[b].append(a)

for i in g.keys():
    g[i].sort()
    

def b_dfs(x, discovered=[]):
    discovered.append(x)
    for vertex in g[x]:
        if vertex not in discovered:
            discovered = b_dfs(vertex, discovered)
    return discovered


def b_bfs(start_x):
    discovered = [start_x]
    queue = deque([start_x])
    while queue:
        vertex = queue.popleft()
        for w in g[vertex]:
            if w not in discovered:
                discovered.append(w)
                queue.append(w)
    return discovered


a = b_dfs(V)
b = b_bfs(V)

for i in range(len(a)):
    if i == len(a) - 1:
        print(a[i])
        break
    print(f'{a[i]}', end=' ')
for i in range(len(b)):
    if i == len(b) - 1:
        print(b[i])
        break
    print(f'{b[i]}', end=' ')