BFS 알고리즘에서 거리 계산 기능 넣기(C++)

그래프 탐색 문제에서 종종 출발점에서 거리가 얼마나 되는지 측정해야 하는 때가 있다.

https://www.acmicpc.net/problem/5014

이런 문제가 그렇다.

 

기본적인 BFS 코드는 다음과 같다.

void BFS(int begin_node)
{
	queue<int> que;
	que.push(begin_node);
	visit[begin_node] = 1;
	
	while(que.empty() == false)
	{
		int cur = que.front();
		cout << cur << " ";
		visit[cur] = 1;
		que.pop();
		
		for(int i = 0 ; i < MAX_NODE ; i++)
		{
			if(visit[i] != 1 && graph[cur][i] == 1)
			{
				que.push(i);
				visit[i] = 1;
				// 큐에서 뽑을 때 말고 큐에 넣는 순간에 visit 체크 해줘야 큐에 중복으로 넣는걸 방지함
				// 여기서 visit는 방문을 했냐기보다는 큐에 한 번이라도 들어갔냐(고려되었냐) 정도로 생각하면 됨
			}
		}
	}
}

이 때 2차원 배열인 graph와 1차원 배열인 visit는 함수 외부에 선언되어 있는 변수이다.

(물론 BFS 함수 내부에 선언해주어도 괜찮다. DFS의 경우엔 스택 방식 말고 재귀함수로 구현하면 그렇게 하면 안되지만)

그래프를 2차원 배열 말고 도착 노드의 번호가 담긴 vector<int> 형태로 만들 수도 있는데,

이렇게 만들었다면 위 코드를 적절히 변형시켜주면 된다.

 

 

 

 

BFS 동작 방식을 간단히 설명하자면, 처음 방문할 노드를 큐에 넣은 후

큐가 모두 빌 때까지 반복하는데, 큐에서 노드를 하나 뽑아내서

그 노드와 연결되어있는 모든 노드 중 방문한 적 없는 노드를 새로 큐에 집어넣는다.

큐가 모두 비었다면 방문할 수 있는 모든 노드를 방문한 것이다.

 

왜 큐를 이용하는 방식이 BFS 작동 매커니즘을 표현하게 되는 것인지에 대해서는

이 글에서는 설명하지 않을 것이니 혹시 궁금하다면 다른 곳에서 찾아보길 바란다.

 

 

 

 

아무튼 여기서 다음과 같은 조건만 추가시켜주면 BFS를 실행하며 거리를 계산해낼 수 있다.

모든 노드까지의 최소 거리를 무한대로 초기값 가정을 한 다음,
현재 노드에서 이어진 새로운 노드를 탐색할 때마다(BFS 코드에서 큐에 노드를 넣을 때)
현재 노드까지의 거리 + 1 VS 탐색할 노드의 현재 최소 거리로 여겨지는 값
비교를 하여 작은 값을 선택

 

다음 코드는 거리 계산 기능이 들어있는 BFS 이다.

////// 추가된 부분 /////
int dist[NODE_NUM];
/////////////////////

void BFS(int begin_node)
{
	queue<int> que;
	que.push(begin_node);
	visit[begin_node] = 1;
	
	while(que.empty() == false)
	{
		int cur = que.front();
		cout << cur << " ";
		visit[cur] = 1;
		que.pop();
		
		for(int i = 0 ; i < MAX_NODE ; i++)
		{
			if(visit[i] != 1 && graph[cur][i] == 1)
			{
				que.push(i);
				visit[i] = 1;
                
                //////////////// 추가된 부분 ///////////////////////////
                if(dist[cur] + 1 < dist[i]) dist[i] = dist[cur] + 1;
                /////////////////////////////////////////////////////
			}
		}
	}
}

 

물론 언급했다시피 dist[ ] 배열은 main 함수 내에서 BFS()를 호출하기 전에

무한대 대신 아주 큰 값(예를 들면 21억)으로 초기화해주어야 한다.

for문으로 초기화해주어도 되지만, fill_n(배열첫주소, 크기, 값) 으로 해주는 것이 편하다.

 

 

 

 

 

 

 

 

 

아래 코드는 초반에 예시로 든 백준 문제 5014 : 스타트링크의 풀이이다.

#include<iostream>
#include <vector>
#include <string>
#include <queue>
#include <sstream>
#include <algorithm>
#include <memory.h>

#define MAX_FLOOR 1000001

using namespace std;

void BFS(int max_floor, int start_floor, int target_floor, int up, int down)
{
	bool visit[MAX_FLOOR]; fill_n(visit, MAX_FLOOR, false);
	int dist[MAX_FLOOR]; fill_n(dist, MAX_FLOOR, 2100000000); // 처음 거리는 모두 무한대
	dist[start_floor] = 0;
	queue<int> que;
	que.push(start_floor);
	visit[start_floor] = true;
	
	while(que.empty() == false)
	{
		int cur_floor = que.front();
		que.pop();
		
		if(cur_floor == target_floor)
		{
			// 도착했으면 현재 최소 거리라고 간주된 값을 출력
			cout << dist[cur_floor]; 
			return;
		}
		
		if(cur_floor + up <= max_floor && visit[cur_floor + up] == false)
		{
			que.push(cur_floor + up);
			visit[cur_floor + up] = true;
			// 큐에 넣을 때(새로운 길을 탐색할 때) 현재 길 + 1의 거리가 현재 최소라고 간주되는 거리랑
			// 비교해서 더 작은 쪽을 넣어주면 됨.
			if(dist[cur_floor] + 1 < dist[cur_floor + up]) dist[cur_floor + up] = dist[cur_floor] + 1;
		}
		if(cur_floor - down > 0 && visit[cur_floor - down] == false)
		{
			que.push(cur_floor - down);
			visit[cur_floor - down] = true;
			if(dist[cur_floor] + 1 < dist[cur_floor - down]) dist[cur_floor - down] = dist[cur_floor] + 1;
		}
		
		
	}
	
	cout << "use the stairs";
}

int main()
{
	int f, s, g, u, d;
	cin >> f >> s >> g >> u >> d;
	BFS(f, s, g, u, d);	
	
	return 0;
}