[백준1260번] DFS와 BFS / Python3

문제

그래프를 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를 그래프에 접목함으로 처음 학습한다는 생각으로 배우면서 풀었다.

우선 N*N의 배열을 만들고 입력되어지는 간선들을 인접행렬에 1로써 표시해준다. 즉, 방향이 없는 그래프이므로 2차원행렬에서 i와 j의 간선이 주어진다면 graph[i][j] = graph[j][i] = 1 이 되는 것이다. 그리고 탐색과정에서 정점의 방문여부를 저장하기 위한 visit배열을 만들어주었다.

[DFS]

깊이 우선 탐색은 말그대로 깊숙히 들어가면서 탐색을 하는 것이다. stack이나 재귀를 가지고 구현을 할 수 있으며, 이 문제에서는 재귀를 이용해서 문제를 풀었다. dfs함수는 방문하려는 노드를 입력으로 받고 해당 노드에 연결된 노드를 작은 수부터 for문을 돌면서 탐색을 한다. for문을 돌면서 아직 방문하지 않은 (visit[v] = 0)이면서 현재 v에서 i로의 간선이 있는지(graph[v][i] == 1)를 확인해 두 조건 모두 만족하면 다시 dfs에 재귀로 입력이 주어지면 된다. 이렇게 깊이 우선 탐색을 구현할 수 있다.

[BFS]

넓이 우선 탐색은 깊이가 아닌 해당 노드에 연결되어있는 모든 노드들을 먼저 탐색하는 것이다. 따라서 queue를 사용하여 구현을 할 수 있다. 이미 dfs에서 방문을 모두 하여 visit배열은 모든 원소가 1로 초기화가 되어있을 것이기 때문에 여기서 방문할 경우에는 0으로 초기화를 시켜주면 된다. bfs는 처음 방문하는 노드를 입력받고 우선 queue에 넣는다. 그리고 queue가 모두 빌때까지 반복을하며 dfs에서와 같은 조건으로 아직 방문하지 않고 간선이 있는 경우의 노드들을 queue에 넣으면서 계속 반복을 해주면 된다. 말보다 코드로 보면 쉽게 이해가 갈 것이다.

코드

# 1260번 DFS와 BFS
import sys

# DFS
def dfs(v):
    print(v, end=' ')
    visit[v] = 1

    for i in range(1,n+1):
        if visit[i] == 0 and graph[v][i] == 1:
            dfs(i)        # 재귀로 깊이 우선 탐색

# BFS
def bfs(v):
    visit[v] = 0
    queue = [v]

    while(queue):
        v = queue.pop(0)        # 반복마다 현재 v노드를 queue 앞에서 pop
        print(v, end=' ')

        for i in range(1,n+1):
            if visit[i] == 1 and graph[v][i] == 1:
                queue.append(i)        # 현재 v 노드에서 접근 가능한 노드를 queue에 push
                visit[i] = 0

# main
n, m, v = [int(x) for x in sys.stdin.readline().split()]

graph = [[0 for _ in range(n+1)] for _ in range(n+1)]
# dfs에서 방문 : 1, bfs에서 방문 : 0
visit = [0 for _ in range(n+1)]

# 정점 추가
for _ in range(m):
    i, j = [int(x) for x in sys.stdin.readline().split()]
    graph[i][j] = 1
    graph[j][i] = 1

dfs(v)
print()
bfs(v)