[백준] 1260번: DFS와 BFS / Python / 깊이우선탐색(DFS) & 너비우선탐색(BFS)

DFS와 BFS

문제

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

입력

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

출력

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

풀이 방법

DFS와 BFS의 개념을 확실히 하고자 문제를 풀어봤다. 개념 정리는 이것이 취업을 위한 코딩 테스트다 with 파이썬을 참고하였다.

DFS

깊이 우선 탐색으로, 가장 깊숙이 위치하는 노드에 닿을 때까지 탐색한 후 다시 돌아가 다른 경로로 탐색하는 알고리즘이다. 스택 자료구조를 이용하며 동작 과정은 다음과 같다.

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

스택을 이용하는 알고리즘이기 때문에 실제 구현은 재귀함수를 이용하면 간단하다. 데이터의 개수가 $N$개인 경우 $O(N)$의 시간이 소요된다.

BFS

너비 우선 탐색으로, 가까운 노드부터 탐색하는 알고리즘이다. 선입선출 방식인 큐 자료구조를 이용하여 구현할 수 있다. 동작 과정은 다음과 같다.

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않는 노드를 모두 큐에 삽입하고 방문 처리를 한다.
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

탐색을 수행함에 있어 $O(N)$의 시간이 소요되며 일반적인 경우 실제 수행 시간은 DFS보다 좋은 편이라고 한다.

from collections import deque

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

# 각 노드가 연결된 정보를 2차원 배열로 표현
graph = [[0] * (n + 1) for _ in range(n + 1)]
for _ in range(m):
    a, b = map(int, input().split())
    graph[a][b], graph[b][a] = 1, 1 
    
def dfs(graph, v, visited):
	# 현재 노드를 방문 처리
    visited[v] = True
    print(v, end=' ')
    for i in range(1, n + 1):
    	# 현재 노드와 연결된 다른 노드를 재귀적으로 방문
        if graph[v][i] == 1 and not visited[i]:
            dfs(graph, i, visited)

def bfs(graph, v, visited):
	# deque 라이브러리 사용
    q = deque([v])
    # 현재 노드를 방문 처리
    visited[v] = True
    # 큐가 빌 때까지 반복
    while q:
    	# 큐에서 다음 노드를 뽑아 출력
        node = q.popleft()
        print(node, end=' ')
        for i in range(1, n + 1):
        	# 현재 노드와 연결된, 아직 방문하지 않은 다른 노드들을 모두 큐에 삽입
            if graph[node][i] == 1 and not visited[i]:
                q.append(i)
                visited[i] = True       

visited = [False] * (n + 1)
dfs(graph, v, visited)
print()
visited = [False] * (n + 1)
bfs(graph, v, visited)