백준 1260 [DFS와 BFS] 파이썬

import sys

input = sys.stdin.readline
N, M, V = map(int, input().split())

d_visited = [0]*(N+1)
b_visited = [0]*(N+1)
link = [[] for _ in range(N+1)]
for _ in range(M):
    a, b = map(int, input().split())
    link[a].append(b)
    link[b].append(a)
    d_visited[b] = 1
    d_visited[a] = 1
    b_visited[b] = 1
    b_visited[a] = 1
for i in range(1, N+1):
    link[i].sort()

# DFS

def dfs(v):
    print(v, end=' ')
    d_visited[v] = 0
    for node in link[v]:
        if d_visited[node] == 1:
            dfs(node)

#BFS

def bfs(v):
    q = []
    q.append(v)
    b_visited[v] = 0
    while(q):
        node = q.pop(0)
        print(node, end=' ')
        for n in link[node]:
            if b_visited[n] == 1:
                b_visited[n] = 0
                q.append(n)


dfs(V)
print()
bfs(V)

 

먼저, 간선들의 정보를 link에 저장하고, 각 노드의 방문여부는 BFS, DFS에 따라 b_visited, d_visited로 분류하였다.

 

그 뒤로, dfs 와 bfs를 사용하여 문제를 해결하였다.

 

생각보다 코드를 잘 짜지 못한거같다. 번호가 낮은 순서대로 방문하기 위해 for문을 돌면서, list를 정렬하는 코드를 작성했는데, 크기가 커진다면 효율성이 좋지 못할거같다...