[백준 1260번] DFS와 BFS - Python

백준 1260문제

문제 파악

 그래프에 대한 정보가 주어진다. 해당 그래프의 노드(정점)들에는 숫자가 주어져있으며 DFS와 BFS 각각의 방법으로 탐색했을때 지나가는 순서를 구해야한다. 이 문제를 푸는 과정은 크게 다음과 같이 단계를 나누어서 접근했다.

1. 입력 데이터들을 사용하기 쉽게 변환하여 그래프 배열을 구한다.
2. DFS와 BFS를 수행하는 함수를 만든다.
3. 그래프와 시작 노드 그리고 DFS, BFS 함수 등을 이용하여 방문하는 노드 순서 출력

 2번의 경우 이전에 DFS, BFS 알고리즘에서 다루었다. 그래서 나머지 부분은 큰 어려움이 없었다. 무엇을 찾아야하는 조건이 없었고 전역 탐색만 수행하면 되었기에 쉬운 문제라고 생각했다. 하지만 이 문제의 관건은 1번이었다. 주어진 입력 데이터들을 2차원 배열로 정리하는 과정이 조금 복잡했다.

문제 풀이

1. 2차원 배열로 표현된 그래프 구하기

 입력으로 주어지는 데이터를 읽을 때 input()을 사용하지 않았다. 그 대신 sys.stdin.readline()를 이용하였는데 그 이유는 속도적인 측면에서 더 빠르기 때문이다. 지금은 못찾겠지만 백준에서 input()과 sys.stdin.readline()를 비교하는 문제가 있었다. 순서대로 주어지는 문자들을 읽어보자.

import sys

# 첫번째 줄 입력값 읽기
n, m, v = map(int, sys.stdin.readline().split())

# 두번째 줄 이후 입력값 읽기
for _ in range(m):
    p1, p2 = map(int, sys.stdin.readline().split())

 첫번째 줄에서 주어지는 간선의 개수인 m을 이용하여 이후로 들어오는 데이터들이 몇 줄인지 알 수 있다. 이를 이용하여 이후의 입력 데이터들을 정확하게 받을 수 있다. 이제 바로 그래프를 구현해보자.

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

for _ in range(m):
    p1, p2 = map(int, sys.stdin.readline().split())
    graph[p1].append(p2)
    graph[p2].append(p1)

 다시 보니 간단해보이지만 조금(?) 막혔던 과정이었다.

2. DFS & BFS 함수 구현

 DFS의 경우 재귀 호출, BFS는 큐 자료구조를 이용하여 구현하였다.

# queue 자료 구조 라이브러리
from collections import deque

# 노드 방문 여부 저장
visited = [False] * (n+1)

# DFS
def dfs(v):
    visited[v] = True
    for i in graph[v]:
        if not visited[i]:
            dfs(i)

# BFS
def bfs(v):
    visited[v] = True
    queue = deque([v])
    while queue:
        v = queue.popleft()
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

3. 노드 순서 출력

 DFS와 BFS 함수 내에서 각 노드를 지나치는 시점마다 해당 지점의 숫자를 저장해두어야한다. 그래서 아래와 같이 result_dfs, result_bfs의 배열을 사용했다.

# DFS 방문 노드 순서
result_dfs = []

def dfs(v):
    visited[v] = True
    result_dfs.append(v) # 노드 방문 저장
    for i in graph[v]:
        if not visited[i]:
            dfs(i)

# BFS 방문 노드 순서
result_bfs = []

def bfs(v):
    visited[v] = True
    queue = deque([v])
    while queue:
        v = queue.popleft()
        result_bfs.append(v) # 노드 방문 저장
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

 

 마지막 과정은 배열에 담긴 숫자를 순서대로 출력하는 것이다. for문 내에서 print를 사용하여 출력할 수 있지만 더 간단한 방법이 있을것 같아서 찾아보았다. 왜냐하면 javascript에서는 있기 때문이다.

arr = [1, 2, 3, 4, 5]

print(arr)
# 결과 : [1, 2, 3, 4, 5]

print(*arr)
# 결과 : 1 2 3

 

 역시 이처럼 편한 방법이 있었다! 기억해두고 써야겠다.

최종 풀이

from collections import deque
import sys

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


def bfs(v):
    visited[v] = True
    queue = deque([v])
    while queue:
        v = queue.popleft()
        result_bfs.append(v)
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

n, m, v = map(int, sys.stdin.readline().split())

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

for _ in range(m):
    p1, p2 = map(int, sys.stdin.readline().split())
    graph[p1].append(p2)
    graph[p2].append(p1)
    
for i in graph:
    i.sort()


visited = [False] * (n+1)
result_dfs = []
dfs(v)

visited = [False] * (n+1)
result_bfs = []
bfs(v)

print(*result_dfs)
print(*result_bfs)

후기

 이 문제는 대놓고 출제된 DFS, BFS 문제여서 재미(?)가 없었다. 개념 설명 바로 뒤에 있는 예제 문제같은 느낌이다. 아무튼 그럼에도 불구하고 꽤 유용한 것들도 배울 수 있었던 기회라고 생각한다.

 배열 요소를 한번에 출력할 수 있도록 도와준 * 의 이름은 Asterisks라고 한다. 좀 더 자세한 내용은 이곳을 찾아보자.

https://treyhunner.com/2018/10/asterisks-in-python-what-they-are-and-how-to-use-them/