백준 - 그래프(# 1260)

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

Code 1

import sys

def dfs(v):
    print(v, end=' ')
    already_visited[v] = 1
    for i in range(1,n+1):
        if adj_matrix[v][i] == 1 and already_visited[i] == 0:
            dfs(i)

def bfs(v):
    already_visited = [0]*(n+1)

    queue = [v]
    already_visited[v] = 1

    while queue:
        v = queue[0]
        del queue[0]
        print(v, end=' ')
        for i in range(1, n+1):
            if adj_matrix[v][i] == 1 and already_visited[i] == 0:
                queue.append(i)
                already_visited[i] = 1

n, m, v = map(int, input().split())
adj_matrix = [[0]*(n+1) for _ in range(n+1)]

for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())
    adj_matrix[a][b] = 1
    adj_matrix[b][a] = 1

already_visited = [0]*(n+1)
dfs(v)
print()

bfs(v)

Code 2

import sys

def dfs(v):
    visited = {}
    stack = [v]

    while stack:
        s = stack.pop()
        if s not in visited:
            visited.setdefault(s)
            stack += reversed(adj_dict[s])

    return visited


def bfs(v):
    visited = {}
    queue = [v]

    while queue:
        s = queue[0]
        del queue[0]
        if s not in visited:
            visited.setdefault(s)
            queue += adj_dict[s]
    
    return visited


n, m, v = map(int, input().split())
adj_dict = {i:[] for i in range(1,n+1)}
for i in range(1,m+1):
    a, b = map(int, sys.stdin.readline().split())
    adj_dict[a].append(b)
    adj_dict[b].append(a)

for k in adj_dict:
    adj_dict[k].sort()

dfs_result = dfs(v)
bfs_result = bfs(v)

print(' '.join(list(map(str, dfs_result))))
print(' '.join(list(map(str, bfs_result))))

참고

Code1
: adjacency matrix를 이용하여 DFS, BFS를 구현하였다.
DFS는 재귀함수로, BFS는 queue로 구현하였다.
이미 방문한 노드를 list에 기록하였다.

Code2:
adjacency list를 이용하여 DFS, BFS를 구현하였다.
DFS는 stack으로, BFS는 queue로 구현하였다.
이미 방문한 노드를 dict로 기록하였다.
이미 방문한 노드를 list에 기록하고 확인하는 것 보다 dict을 이용하는 것이 더 빨랐다. 어떤 원소의 존재 유무를 확인하는 과정이 list보다 dict에서 효율적으로 가능하기 때문이다.
또한, Code 2가 Code 1보다 더 빠르다.