[BOJ] 1260 - DFS와 BFS

문제는 다음과 같다.

🚦 문제 유형

- Graph Traversal (그래프 탐색)

- DFS/BFS

 

✏️ Solution

제목에 DFS/BFS 가 명시된 문제로, 전형적인 DFS/BFS 알고리즘을 그대로 사용해 풀었다.

from collections import deque
import sys
input = sys.stdin.readline

n, m, v = map(int, input().split(' '))

graph = [[] for i in range(n+1)]

for _ in range(m):
    f, s = map(int, input().split(' '))
    graph[f].append(s)
    graph[s].append(f)

visited = [False]*(n+1)
visited2 = [False]*(n+1)

dfs_result = []
bfs_result = []

# dfs
def dfs(v, graph, visited):
    visited[v] = True
    dfs_result.append(str(v))
    graph[v].sort()
    for i in graph[v]:
        if visited[i] == False:
            dfs(i, graph, visited)


# bfs
def bfs(v, graph, visited):
    queue = deque([v])
    visited[v] = True
    while queue:
        now = queue.popleft()
        bfs_result.append(str(now))
        graph[now].sort()
        for i in graph[now]:
            if visited[i] == False:
                queue.append(i)
                visited[i] = True

dfs(v, graph, visited)
bfs(v, graph, visited2)

print(' '.join(dfs_result))
print(' '.join(bfs_result))

 

⚙️ Review

알고리즘 문제집에서 공식처럼 배우는 DFS/BFS 코드를 기억한다면 풀 수 있는 문제이다. DFS는 익숙해서 금방 짰지만 BFS는 상대적으로 조금 더 걸렸다. 의외로 빼먹은 줄도 많았고 한번에 성공하지 못했다.

1. BFS 기억할 것

• 큐에서 노드를 pop 하고 인접 노드 중에 방문한 노드가 있는지 확인한 후 append 하기.

2. input 처리에서 기억할 것

• input() 함수보다 sys.stdin.readline 이 훨씬 빠르다.
• sys.stdin.readline, sys.stdin.readline(), sys.stdin.readlines()의 차이점을 확실히 알아야 한다.
  👉 이것 때문에 입력에서 에러가 났었음.
• sys.stdin.readline 차이점(링크)