[백준] DFS와 BFS(python)

백준, DFS와 BFS

TL;DR

• 깊이 우선 탐색(DFS)
• 너비 우선 탐색(BFS)

문제 분석

1. 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오.
2. 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고
3. 더 이상 방문할 수 있는 점이 없는 경우 종료한다.
4. 정점 번호는 1번부터 N번까지이다.

 

- 입력으로 주어진 그래프를 DFS와 BFS로 각각 순회한 결과를 출력하는 프로그램을 작성하는 문제이다.

- 2번의 조건에 유의하여 문제를 풀어야 한다.

입출력 형태

입출력 예시

 

- 가장 첫 번째 줄에 정점(vertex, node)의 개수와 간선(edge)의 개수, 그리고 시작 정점의 번호가 주어진다.

- 두 번째 줄부터는 각 정점 간의 연결관계를 나타내는 값들이 주어진다. 문제 조건에 따라 그래프는 양방향을 갖고 있다.

 

풀이

from collections import deque

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

for _ in range(m):
    _v, e = map(int, input().split())
    graph[_v].append(e)
    graph[e].append(_v)

for i in graph:
    i.sort()

def dfs(vertex, visits):
    visits.append(vertex)
    for w in graph[vertex]:
        if w not in visits:
            visits = dfs(w, visits)
    return visits

def bfs(start_v):
    discovered = [start_v]
    queue = deque()
    queue.append(start_v)
    while queue:
        top = queue.popleft()
        for _w in graph[top]:
            if _w not in discovered:
                discovered.append(_w)
                queue.append(_w)        
    return discovered

print(*dfs(v, []))
print(*bfs(v))

 

- 그래프가 양방향 그래프이기 때문에 하나의 간선 연결에 대해 두 가지 정점이 모두 연결되도록 그래프를 입력받는다.

- 이 때, index는 정점이 되고 index에 해당하는 값은 해당 정점과 연결 관계가 있는 정점들을 나타낸다.

- 연결 관계가 있는 정점들을 한 번 정렬해준다. 그 이유는 방문할 수 있는 정점이 여러 개인 경우 번호가 낮은 순서부터 방문하기 때문이다.

- 재귀적으로 구현한 DFS와 큐를 사용하여 BFS를 구현한다.

  - DFS의 경우, 리스트 visits에 방문한 정점을 저장하고, 해당 정점과 연결된 정점들을 조회하며 재귀적으로 동작한다.

  - BFS의 경우, 큐를 사용하여 정점들을 조회한다.

-출력을 할 때 처리가 중요하다. DFS, BFS 함수에서의 반환값은 리스트의 형태로 반환되는데 문제에서 원하는 형식의 반환은 리스트의 형태가 아니다. 따라서 *을 붙여 리스트를 언팩(unpack)한 결과를 출력해준다. 아니면 `join` 메소드를 사용하여 출력해도 된다.