[알고리즘 자습]그래프(Graph) - 1. BFS(너비우선탐색)의 정의와 활용, 예제, 파이썬(Python3)

코딩테스트를 준비하는 사람이든 아니든, 프로그래밍에 발을 들여본 적이 있는 사람들은 무조건 들어봤을 것이다. 너비 우선 탐색, BFS이다. 코딩테스트 단골 문제이기도 하고, 백준 및 프로그래머스에서도 굉장히 많은 문제가 준비되어 있다. 문제가 많다는 것인 즉슨 연습할 기회가 충분히 주어져 있다는 뜻이다. 근데 나는 옛날에 배웠던 BFS가 정확히 기억이 나지를 않아서, 쉬운 문제도 풀지 못했다. 그래서, 한번 정리를 하고자 한다. 혹시, 이 글을 읽는 사람이 BFS가 뭔지는 들어는 봤고, 너비우선 탐색이라 한 노드에 연결되어있는 다른 노드들을 방문한 다음에 이러쿵저러쿵... 이렇게까지 설명은 할 수 있지만, 당장 구현을 못하겠다라는 생각이 든다면 나와 같이 이글을 쭉 읽어보자. 

그래프 순회 알고리즘

전 게시물에서, 그래프 자료구조에 대해 알아봤다(만약 그래프 자료구조에 대해 잘 모르겠다면, 아래의 링크를 따라가시오). 우리가 데이터를 목적에 맞게 저장하고 필요할 때 사용하기 위해서, 그래프 형태, 즉 정점의 집합과 간선의 집합의 형태로 저장을 했다. 그런데, 이렇게 저장만 해놓는다면 그 데이터는 쓸모가 없다. 데이터를 저장했으니, 어떻게 사용하는 지에 대해 생각을 해봐야 한다.

리스트에 데이터를 저장했다면, 그 리스트의 모든 원소의 값을 확인하면서 문제의 요구에 맞는 답을 출력해야 하는 경우가 많다. 이것이 우리가 그래프 순회 알고리즘을 배워야 하는 이유이다. 데이터를 사용하려면, 일단 데이터가 어떤 것들이 있는지를 알아야 한다. 그러기 위해서는, 그래프의 모든 정점을 순회해야 하는 경우가 대단히 많다. 그 중 대표적인 알고리즘이 바로 BFS, DFS인 것이다. 

2020/02/28 - [공부/알고리즘] - [알고리즘 자습]그래프(Graph) - 0. 자료 구조

[알고리즘 자습]그래프(Graph) - 0. 자료 구조

 

BFS(너비 우선 탐색)

너비 우선 탐색이란, 하나의 시작 정점을 방문한 후, 시작 정점에 인접한 정점들을 우선 방문하는 방법이다. 더 이상 방문할 수 있는 노드가 없을때(이전에 방문하지 않은 노드가 없거나, 더 이상 인접한 노드가 없을 때) 탐색을 종료한다. 

 

https://commons.wikimedia.org/wiki/File:Animated_BFS.gif

 

위키피디아에서 퍼온 위의 애니메이션을 보면 정말 한 눈에 알 수 있다. 좀 더 첨언을 하자면, 정점이 검정색으로 변하는 것은 그 노드를 방문했다는 뜻이고, 회색으로 변하는 것은 큐에 노드를 집어 넣었다는 뜻이다. 다음과 같은 변수를 사용해서 데이터를 저장할 것이다. 

visited 배열: 정점의 갯수만큼의 원소를 갖는다. 각 원소를 True이거나 False값을 갖는데, True라면 방문한 노드라는 뜻이고, False라면 아직 방문하지 않았다는 뜻이다. 

queue: 선입선출의 자료구조인 큐이다. 어느 한 정점을 방문했을때, 그 정점과 인접한 정점을 큐에 집어 넣어놓는다. 

위 변수들을 가지고 아래와 같은 흐름을 따른다. 이해를 돕기 위해, 글로 쓰도록 하겠다. 코드는 뒤에 나오니까 관심 없으면 쭉 내려서 보기 바란다. 

1. 시작 정점을 queue에 넣는다. 
2. visited[start] = True로 함으로써 , start노드를 방문했다고 표시한다.

정말 간단하다. 근데 이렇게 죽죽 읽으면 너무 당연한데, 막상 해보면 손이 꼬여서 잘 안될 수 있으니, 아래 예제도 꼭 해보길 바란다. 

 

예제1: 주어진 그래프를 BFS로 순회하기

---

 

이렇게 생긴 그래프를 BFS를 통해 순회해보자

 

입력

• 그래프의 인접 행렬

[[1, 1, 1, 1, 0, 0],
[1, 1, 0, 0, 0, 0],
[1, 0, 1, 0, 0, 1],
[1, 0, 0, 1, 1, 0],
[0, 0, 0, 1, 1, 0],
[0, 0, 1, 0, 0, 1]]

• 시작 정점

출력

• 그래프를 방문하는 순서

---

정말 기본적인 BFS이다. 이 문제를 꼭 자기손으로 짜봐야 하는 이유는, 이것도 자기 손으로 못짜면, 조금만 응용된 문제가 나와도 어디를 건드려서 튜닝을 해야 알지 감이 전혀 오지 않는다. 이건 내 경험담이다. 그러므로 코드를 짜보면 다음과 같다. 

def bfs(graph, input_start):
    visited = [False] * len(graph)
    answer = []
    
    queue = [input_start]
    visited[input_start] = True
    while queue:
        node = queue.pop(0)
        answer.append(node)
        for i in range(len(graph[node])):
            if graph[node][i] == 1 and not visited[i] and node != i:
                queue.append(i)
                visited[i] = True
	return answer
   
graph = [[1, 1, 1, 1, 0, 0],
         [1, 1, 0, 0, 0, 0],
         [1, 0, 1, 0, 0, 1],
         [1, 0, 0, 1, 1, 0],
         [0, 0, 0, 1, 1, 0],
         [0, 0, 1, 0, 0, 1]]

start = 0
print("bfs 결과: ", bfs(graph, start))

위의 코드를 실행해보면 다음과 같은 결과를 얻을 수 있다. while문 내부에 for문이 좀 중요한데, 설명을 덧붙이자면 
graph[node], 즉 graph의 0번째 원소인 배열 [1, 1, 1, 1, 0, 0]을 돌겠다는 뜻이다. 이는, 0과 인접한 노드를 찾기 위함이다. graph[node] 배열 안에서, 값이 1인 원소의 인덱스는 1번노드와 인접한 노드라는 뜻이다. 그리고, visited[i]가 False라는 것은 아직 방문되지 않은 노드를 말한다. 그리고 자기 자신과의 연결은 고려하지 않으므로, node != i라는 조건을 넣었다. 

 

 

이해를 조금 돕기 위해, 노드를 방문할 때 방문한 노드의 번호를 print문으로 찍어보겠다. 또한, queue가 어떻게 생겼는지도 print문으로 출력해서, 콘솔창을 통해 확인해보자

 

 

정말 만족할만한 결과가 나오는 것을 알 수 있다. 

 

 

예제2: 주어진 그래프의 시작 정점에서부터, n번만에 갈 수 있는 노드 찾기

---

 

이렇게 생긴 그래프를 BFS를 통해 순회해보자

 

입력

• 그래프의 인접 행렬, 시작 정점, n

[[1, 1, 1, 1, 0, 0]

• 시작 정점

출력

n번만에 갈 수 있는 노드들

---

이 예제는, 1번에서 약간의 응용을 더한 문제다. 아래와 같이 코드를 작성하면 풀 수 있다. 

def solution(graph, input_start, n):
    visited = [False] * len(graph)
    queue = [input_start]
    visited[input_start] = True
    count = 0

    while queue:
        print("queue: ", queue)
        count += 1
        new_arr = []
        for i in queue:
            node = i
            for j in range(len(graph[node])):
                if graph[node][j] == 1 and not visited[j] and node != j:
                    new_arr.append(j)
                    visited[j] = True

        queue = new_arr
        if count == n:
            return new_arr


graph = [[1, 1, 1, 1, 0, 0],
         [1, 1, 0, 0, 0, 0],
         [1, 0, 1, 0, 0, 1],
         [1, 0, 0, 1, 1, 0],
         [0, 0, 0, 1, 1, 0],
         [0, 0, 1, 0, 0, 1]]
n = 3
start = 1
print(solution(graph, start, n))

1번의 코드와 크게 다를것은 없다. 다만 추가로 고려해야 할 점은, queue에 값이 여러 개 있을 때, queue에 있는 모든 노드의 인접 노드를 찾아야 한다. 그리고 그 인접 노드들을 담은 new_arr을 queue에 할당해서 넘겨줘야 한다. 즉, 0번에서 bfs를 했을 때, 큐에는 [1,2,3]이 담긴다. 그 상태에서 1을 pop 하고 1과 인접 노드를 찾으면, 1과 인접 노드는 더 이상 없으므로, 큐에는 [2,3]이 남는다. 그리고 2를 pop하고, 5를 큐에 담으므로, 큐에는 [3, 5]가 담기게 된다. 

여기서 문제가 생긴다. 분명히 5는 0번 노드에서 2번만에 갈 수 있는 노드이고, 3은 0번 노드에서 1번만에 갈 수 있는 노드인데 이 둘이 한 배열에 담긴다면 우리는 어떤 노드가 몇 번만에 도착할 수 있는 노드인지를 구별할 수가 없다. 이를 표로 나타낸 것이 아래이다. 

시작 정점을 1로 하자. 1번 예제의 코드를 실행할 경우, 

 

 

위의 경우에선, BFS를 3번 실행한 결과에서 [5, 3]이 같이 담기는 것을 볼 수 있다. 

이렇게 흘러간다. 

2번 예제의 코드를 실행할 경우, 

 

 

위 표에서, 3번 BFS를 하고 난 뒤 만들어지는 new_arr이 비어있으므로, 더이상 반복을 하지 않고 중단한다. 

 

 

 bfs의 시간복잡도는 인접 행렬의 경우 O(N^2)이다. 인접 리스트의 경우는 O(V + E)이다(V는 정점의 갯수, E는 간선의 갯수). 따라서, 노드의 갯수가 많다면 그래프를 인접 리스트로 표현해서 풀기를 바란다. 코드는 위에 쓰인 코드들과 크게 다르지 않으니, 연습삼아 구현해봐도 좋다.

 

활용

BFS DFS를 나누는 것이 의미가 있나 싶긴 하지만, 그래도 BFS를 쓰는 것이 더 나은 경우는 보통 최소 몇번만에 원하는 노드에 도착할 수 있느냐이다. 이 부분은 DFS부분을 설명하면서 비교하면서 서술하도록 하겠다. 

 

 

이렇게 BFS를 살펴 보았다. 분명 이 글을 다 읽었다면,  읽은이가 먼 과거에 학교에서 배웠던 것과 이 게시물을 바탕으로  새로운 영감을 얻기를 바란다.