[BOJ 1260] DFS 와 BFS

기록 상 한 달 전에 풀었다고 되어 있는데.. 기억이 전혀 나질 않는다.

한 달 동안 과연 무슨 일을 했던 걸까.

 

겨우겨우 다시 공부를 해서 이번엔 DFS, BFS를 혼자 구현할 수 있게 되었다.

DFS 는 스택 대신 재귀 함수를 사용했으며, BFS는 queue를 사용하여 구현했다.

 

from collections import deque


def make_graph(node, edge):
    graph = [[] for _ in range(node + 1)]
    for _ in range(edge):
        n, m = map(int, input().split())
        graph[n].append(m)
        graph[m].append(n)
    for i in range(len(graph)):
        graph[i].sort()
    return graph


def dfs(graph, start_node, visited, v=[]):
    visited[start_node] = True
    v.append(start_node)
    for i in graph[start_node]:
        if not visited[i]:
            dfs(graph, i, visited, v)

    return v


def bfs(graph, start_node, visited):
    visited[start_node] = True
    v = [start_node]
    queue = deque([start_node])

    while len(queue) != 0:
        top = queue.popleft()
        for i in graph[top]:
            if not visited[i]:
                visited[i] = True
                v.append(i)
                queue.append(i)
    return v


N, M, V = map(int, input().split())
G = make_graph(N, M)

dfs_visited = [False] * (N + 1)
bfs_visited = [False] * (N + 1)

dfs_result = dfs(G, V, dfs_visited)
bfs_result = bfs(G, V, bfs_visited)

for i in dfs_result:
    print(i, end=" ")
print()
for i in bfs_result:
    print(i, end=" ")

 

어제는 not in 을 사용했는데 O(n)의 시간 복잡도라는 것을 알게 되어서 방문 flag(visited)를 두고 O(1)로 방문 여부 확인 시간 복잡도를 줄였다.