[🥈2 / 백준 1260 / 파이썬] DFS와 BFS

 

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
예제 입력 3  1000 1 1000 999 1000	예제 출력 3  1000 999 1000 999

 

풀이

 

그래프를(트리가 아님) DFS와 BFS로 순환하여 거친 정점들을 차례대로 출력하는 문제이다.

 

DFS와 BFS에는 크게 인접 행렬 방식과 인접 리스트 방식이 존재한다.

 

인접 행렬 방식은 i, j 노드끼리 연결되어 있다면 2차원 배열인 A 배열에 A[i][j], A[j][i] 를 1로 기록하여

서로 연결되어있음을 표시하는 방식이다. 

 

인접 리스트 방식은 1차원 배열인 A 배열에 정점 i에 연결된 정점들을 A[i] = {1,2,3} 과 같은 방식으로

쭉 기록하는 방식이다.

 

인접 행렬 방식은 배열은 n^2 만큼 구성하고, 순회할 때 배열의 모든 자료를 한 번씩 검사해야 하므로

시간복잡도가 O(N^2)인 반면, 인접 리스트는 명시되어있는 리스트만큼 순회하면 되므로

시간복잡도가 O(N + E)에 해당한다.

 

따라서 경우에 따라 다르지만, 보통 인접 리스트 방식이 효율성이 더 좋다고 할 수 있겠다.

 

이번 문제에서는 인접 행렬 방식을 통해서 DFS와 BFS를 구현해보았다.

 

DFS는 재귀를 통해 구현이 가능하다.

반면 BFS는 재귀와 더불어 큐를 사용하여 구현해야 한다.

BFS로 인접 정점들을 탐색한 뒤, 다시 첫 번째로 탐색한 인접 노드부터 다른 정점들을 탐색해야 하기 때문이다.

 

풀이에서는 그냥 본인 편의상 덱을 사용했다.

 

아울러, 트리가 아닌 그래프이기 때문에 재귀를 한다면 어느 정점부터 시작했는지 알 수 없는 구간이 오게 된다.

그러므로 방문했던 정점들을 기록해놓는 리스트를 하나 만들어두고, 방문하지 않은 정점들만 새로 방문하면 된다.

 

 

 

from collections import deque
import sys
# 재귀 제한에 걸리므로 제한을 풀어줘야 한다.
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

n,m,v = map(int,input().split())
l = [list(map(int,input().split())) for i in range(m)]

# 정점의 번호를 인덱스로 그대로 사용하기 위해 한 개 만큼 크게 만들어주었다.
graph = [[0 for i in range(n+1)] for i in range(n+1)]
d_visit = []
b_visit = []

deq = deque()

# 인접 행렬로 그래프를 표현
for i,j in l:
    graph[i][j] = 1
    graph[j][i] = 1

def dfs(v):
    if v not in d_visit:
        d_visit.append(v)
    else:
        return
    
    for i in range(1,n+1):
        if graph[v][i]:
            dfs(i)
            
def bfs(v):
    if v not in b_visit:
        b_visit.append(v)
        
    for i in range(1,n+1):
        if graph[v][i] and i not in b_visit:
            deq.append(i)
            b_visit.append(i)
            
    if deq:
        bfs(deq.popleft())

dfs(v)
bfs(v)
print(*d_visit)
print(*b_visit)