백준(Baekjoon) 1260번 DFS와 BFS 문제 풀이 | Python 파이썬 알고리즘

DFS와 BFS

출처: www.acmicpc.net/problem/1260

1260번: DFS와 BFS

문제

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

입력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

출력

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

예제 입력1

4 5 1
1 2
1 3
1 4
2 4
3 4

예제 출력1

1 2 4 3
1 2 3 4

예제 입력2

5 5 3
5 4
5 2
1 2
3 4
3 1

예제 출력2

3 1 2 5 4
3 1 4 2 5

풀이

DFS와 BFS를 함수로 구현할 수 있다면, 이제 graph를 입력 값으로 받고 딕셔너리로 만드는 부분만 구현하면 완성할 수 있다.

먼저, 문제를 풀기 전 DFS와 BFS를 완전히 이해하고 있는지 확인해보는 과정이 필요하다.

아래에 DFS와 BFS에 대해 간단하게 정리해보았다.

DFS(Depth First Search): 깊이 우선 탐색

: 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법

▶ 넓게(wide) 탐색하기 전에 깊게(deep) 탐색하는 것

▶ 모든 노드를 방문하고자 하는 경우에 이 방법을 선택.

▶ 깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단하지만, 속도는 BFS에 비해 느리다.

BFS(Breadth First Search): 너비 우선 탐색

: 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법

▶깊게(deep) 탐색하기 전에 넓게(wide) 탐색하는 것

▶ 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택

▶ 너비 우선 탐색(BFS)이 깊이 우선 탐색(DFS)보다 좀 더 복집하지만, 속도는 BFS에 비해 빠르다.

 

**BFS 알고리즘의 핵심은 큐(Queue)를 사용하는 것인데,

여기서 알아둬야할 것은 큐를 list.pop(0)를 사용하는 것과 같이 구현하면 시간 복잡도가 O(N)이라 시간적으로 매우 비효율적인 코드가 만들어지게 된다고 한다.

따라서 collections 라이브러리의 dequeue를 사용하면 시간을 절약할 수 있다.

 

아래는 백준 1260번을 구현한 코드이다.

from collections import deque
def DFS(graph, root):
    visited = []
    stack = [root]
    while stack:
        n = stack.pop()
        if n not in visited:
            visited.append(n)
            if n in graph:
                temp = list(graph[n] - set(visited))
                temp.sort(reverse=True)
                stack += temp
    return " ".join(str(i) for i in visited)

def BFS(graph, root):
    visited = []
    queue = deque([root])
    while queue:
        n = queue.popleft()
        if n not in visited:
            visited.append(n)
            if n in graph:
                temp = list(graph[n] - set(visited))
                temp.sort()
                queue += temp
    return " ".join(str(i) for i in visited)



#graph를 딕셔너리로 만들기
n,m,start=map(int,input().split())
graph=dict.fromkeys(range(1,n+1))
value=[[] for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    value[a-1].append(b)
    value[b-1].append(a)
for i in range(n):
    graph[i+1]=set(value[i])
#DFS/BFS 함수 적용
print(DFS(graph, start))
print(BFS(graph, start))

 

참고:

gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html

cyc1am3n.github.io/2019/04/26/bfs_dfs_with_python.html