[백준/1260/파이썬3(python3)] DFS와 BFS

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

문제

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

입력

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

출력

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

입출력 예

입력	출력
4 5 1 1 2 1 3 1 4 2 4 3 4	1 2 4 3 1 2 3 4

개념

내가 처음 만나게 된 그래프 탐색 문제이다. DFS가 뭔지, BFS가 뭐지도 몰랐던 상태에서 만나게 된 문제라 굉장히 당혹스러웠지만 읽어보니 예전에 정보처리기사 땄을 때 공부한 거였다. 이제부터 이 문제를 풀기 위해 알아야 할 개념들을 하나씩 나열해보겠다.

1. DFS는 깊이우선탐색(Depth First Search)이고 BFS는 너비우선탐색(Breadth First Search)를 의미한다.
   
   

2. 위 입력으로 주어진 그래프를 이해하기 쉽게 그려보면 다음과 같다.
   

   
   생각없이 그리다가 이런 모습들이 되었지만... 

   

   이게 합리적이고 납득할 수 있는 모습일 것이다.
   
   

3. 출력을 보면 알 수 있다시피 DFS는 다음과 같은 과정으로 탐색이 진행되었다.

   

   말 그대로 제일 깊은 곳까지 내려갔다가 다시 분기점으로 올라와서 가지 않았던 길을 다시 가보는 식의 탐색방법이라고 보면 되겠다.
   
   

4. 마찬가지로 BFS는 다음과 같은 과정으로 탐색이 진행되었다.
   

   

   
   

5. 위에 주어진 노선도를 코드로 구현하려면 "인접행렬(Adjacency Matrix)"이라는 것을 알아야 한다. 인접행렬이란 자료형의 일종으로 그래프 이론에서 어느 노드들끼리 연결되었는지를 나타내는 이차원 행렬을 의미한다. 그림으로 그려져있는 저 트리를 컴퓨터가 이해할 수 있게 만들어주는 과정이라고 보면 될 것이다.

   	1	2	3	4
   1	0	1	1	1
   2	1	0	0	1
   3	1	0	0	1
   4	1	1	1	0

   정석으로 그리자면 다음과 같은 모습이다. 1번은 2, 3, 4와 연결돼있으므로 1번 행과 열의 2, 3, 4에 해당하는 칸에 1이라고 적혀있다. 바깥쪽 범례(1,2,3,4)를 제하고 0과 1로만 이뤄진 부분이 인접행렬이다. 코드로 보자면 이런 모습이라 할 수 있겠다.

   adjacency_matrix = [[0, 1, 1, 1],
                       [1, 0, 0, 1],
                       [1, 0, 0, 1],
                       [1, 1, 1, 0]]
   

   하지만 코드상 배열의 시작은 항상 0이기 때문에 위 코드로 그래프를 구현하면 노드1번을 인덱스 0으로, 2를 1로, 3을 2로(and so on-) 표현해야해서 혼동이 일어나기 쉬우므로 대게 코드상 인접행렬을 구현할 땐 index를 그대로 value로 가져가는 경우가 많다. 그러니까 결국 이런 모습이 되는 것이다. 테이블로 구현했을 땐

   	0	1	2	3	4
   0	0	0	0	0	0
   1	0	0	1	1	1
   2	0	1	0	0	1
   3	0	1	0	0	1
   4	0	1	1	1	0

   코드로 구현했을 땐

   adjacency_matrix = [[0, 0, 0, 0, 0],
       				[0, 0, 1, 1, 1],
                       [0, 1, 0, 0, 1],
                       [0, 1, 0, 0, 1],
                       [0, 1, 1, 1, 0]]
   

   이 되는 것이다. 이러면 인덱스와 벨류가 딱 맞아 떨어져 구현하기 쉬워진다. 이제 위 추상적인 노드 그림을 2차원배열로 구현할 수 있게 되었으니 본격적으로 코드를 통해 탐색방법을 구현해보자.

풀이

N, M, V = map(int, input().split())
matrix = [[0] * (N + 1) for _ in range(N + 1)]
for _ in range(M):
    link = list(map(int, input().split()))
    matrix[link[0]][link[1]] = 1
    matrix[link[1]][link[0]] = 1


def dfs(current_node, row, foot_prints):
    foot_prints += [current_node]
    for search_node in range(len(row[current_node])):
        if row[current_node][search_node] and search_node not in foot_prints:
            foot_prints = dfs(search_node, row, foot_prints)
    return foot_prints


def bfs(start):
    queue = [start]
    foot_prints = [start]
    while queue:
        current_node = queue.pop(0)
        for search_node in range(len(matrix[current_node])):
            if matrix[current_node][search_node] and search_node not in foot_prints:
                foot_prints += [search_node]
                queue += [search_node]
    return foot_prints


print(*dfs(V, matrix, []))
print(*bfs(V))

설명

최대한 직관적으로 읽을 수 있게 작성하였다. 비어있는 매트릭스에 주어진 그래프로 인접행렬을 생성하고 DFS방식과 BFS방식으로 탐색한다. DFS방식은 간선이 연결돼있는 노드를 발견하면 다시 또 DFS방식으로 탐색을 시작하는 재귀형식으로 구현되었다. 정확한 흐름을 파악하고 싶다면 주어진 예제에서 DFS방식과 BFS방식의 분기점이 생기는 2번 노드에서의 흐름을 직접 읽어보는 게 좋다.

 

 

P.S : 처음 풀어보는 그래프 문제여서 공부할 게 많았다. 사실 백준 알고리즘을 풀 때 사람들이 많이 풀었지만 나는 아직 풀지 못 한 문제를 순서로 푸는데 이 문제 때문에 다소 지체됐었다. 알아야할 게 많으니 괜히 하기 싫어져서말이다. 뭔가 스스로를 채찍질하는 계기가 됐다. 그리고 맨날 같은 일을 하는 요즘 오랜만에 머리써서 자극이 되고 재미있었다.