알고리즘_BFS(너비우선탐색)

대표적인 두 가지 그래프 탐색 알고리즘 중 하나인 BFS에 대해서 알아보자. (나머지 하나인 DFS는 여기서 확인할 수 있다.)

BFS는 한 정점으로부터 시작해 '넓게 퍼져가며' 그래프를 탐색하는 이미지다. 조금 더 명확하게는, 한 정점과 직접적으로 연결된 모든 정점을 탐색한 뒤 방금 탐색한 정점들과 연결된 다른 정점들을 탐색하면서 연쇄적으로 탐색이 일어나는 방식이다.

BFS의 과정을 아래처럼 그래프로 보면 한 점에서부터 시작해 간선 하나로 연결된 인근한 정점, 그다음은 간선 두개로 연결된 정점들로 탐색 대상이 점점 퍼져나가는 형태가 된다.

시작점과 연결된 두 정점을 먼저 탐색한다.

그다음은 방금 탐색한 두 점과 연결된 다섯 개의 점을 탐색한다.

그다음은 다섯 점 중 2번째 점과 연결된 나머지 한 점을 마저 탐색한다.

 

BFS는 '탐색 예정'의 정점들에 대해 그와 연결된 (방문하지 않은) 다른 정점들을 방문하는 과정을 반복적으로 수행하는 탐색 과정으로도 볼 수 있으므로, 탐색 예정 정점들을 저장해두는 큐(queue)를 구축함으로써 구현할 수 있다. 재귀함수로도 구현할 수 있겠지만, 여러 코드를 짜보고 읽어본 결과 while문을 사용하는 것이 가장 간편하게 느껴졌다. 이를 간단하게 의사 코드로 나타내보면 다음과 같다.

 

queue = [시작 정점(들)]

while (queue에 원소가 존재할 때):
    P에 queue의 맨 앞의 정점을 꺼내 저장한다
    P를 방문했다고 표시
    
    i에 P와 연결된 모든 정점들을 대입해가며:
    	i를 아직 방문하지 않았다면:
        	queue의 맨 끝에 i를 삽입

 

위 코드의 실행 과정을 따져보자. 우선 queue에 저장된 초기 정점들을 하나하나 빼가고 그와 연결된 다른 점들을 탐색 예정 리스트인 queue에 집어넣는다. 큐의 선입선출 원리에 따라, 초기 정점들이 모조리 빠지면 초기 정점들에 의해서 추가된 다음 점들과 연결된 점들을 다시 하나하나 queue에 저장한다. 그러다가 더 이상 갈 곳이 없는 점까지 도달하면 queue에 아무런 탐색 예정 정점을 추가하지 못할 것이고, 모든 갈 수 있는 정점을 다 방문한 뒤에는 queue가 완전히 비게 되어 탐색이 종료된다.

 

BFS는 위에서 말한 '퍼져나가는 듯한' 탐색 성질에 의해 어떤 존재가 그래프 안에서 퍼져나가는 문제에서 적용이 가능하다. 이런 문제들에서는 시작 정점과 한개의 간선, 두개의 간선...으로 연결된 정점들로 '층'을 나눌 수 있으므로 시간에 따른 탐색 경과도 이용할 수 있기도 하다. 그리고 또 대표적인 BFS의 응용으로는 가중치가 없는 그래프에서 최단 거리를 구할 수 있다는 점에 있다. BFS로 시작점에서 어떤 특정한 점까지 도달했을 때, 그 점까지 이동한 간선의 개수가 최단 거리(간선 개수)가 된다. 증명은 아래와 같다.

 

증명) BFS로 시작점 P에서 목표점 A까지 도달하는데 n개의 간선을 거쳤다. 이때 n보다 더 적은 개수인 k개의 간선으로 A에 도달할 수 있었다면(귀류법), 이 경로를 P, P1, P2, ... Pk-1, A(=Pk)로 정의하자.

이때 P부터 P1까지 BFS를 돌렸다고 하면 간선 하나를 거쳤을 것이다. 그다음 P2는 만약 P랑 직접 연결되어 있었다면 간선 하나를 거쳤을 것이고, 그렇지 않다 해도 P1과 연결되어있기 때문에 많아봐야 P와 간선 두 개로 연결된 점들을 탐색하는 단계에서 탐색당하게 된다. 똑같이 P3은 많아봐야 간선 3개, P4는 4개, ... 그리고 A는 많아봐야 k개의 간선을 탐색하는 과정에서 탐색당한다.

그런데 이렇게 BFS로 k번째 이하의 단계에서 A에 도달할 수 있었다면 BFS로 A까지는 k 이하의 간선을 거쳐서 도달하게 되고, 이는 k보다 큰 n개의 간선을 거쳐서 A에 도달했다는 최초 가정에 위반된다. (k 이하의 단계에서 A를 방문했으니 이미 방문한 점을 n단계에서는 절대 방문할 수 없다)

따라서 BFS로 목표점에 n개의 간선(단계)에 거쳐 도달했다면, n 미만의 간선을 거쳐서 목표점에 도달하는 것은 불가능하므로 최단 거리는 n이다.