BFS

저번에는 DFS를 다루었으니, 이젠 그래프 탐색 알고리즘 중 BFS를 다뤄봅시다 !

 

BFS (Breadth First Search)

너비우선탐색, 특정 노드부터 시작해 다음 깊이의 노드로 이동하기 전에 현재 깊이의 모든 정점을 탐색합니다.

이때, 방문한 정점은 다시 방문하지 않으며 보통 "같은" 가중치를 가진 그래프에서 최단거리 알고리즘으로 쓰입니다.

 

pseudocode (수도코드 - 의사코드) - 2가지 버전이 존재합니다.

 

ver1. 방문처리만 하는 BFS 코드

BFS(G, u)
    u.visited = true
    q.push(u);
    while(q.size())
        u = q.front()
        q.pop()
        for each v ∈ G.Adj[u]
            if v.visited == false
                v.visited = true
                q.push(v)

 

 

ver2. 최단거리도 계산하는 BFS 코드

BFS(G, u)
    u.visited = 1
    q.push(u);
    while(q.size())
        u = q.front()
        q.pop()
        for each v ∈ G.Adj[u]
            if v.visited == false
                v.visited = u.visited + 1
                q.push(v)

 

참고로 거리는, 지나온 간선(==화살표)의 개수를 의미합니다.

 

 

BFS 동작 방식에 대한 이해를 돕기 위해 전에 DFS 설명할 때 들었던 예시로 설명해보겠습니다.

같은 너비를 먼저 다 훑고 나서, 다음 너비(level)을 훑습니다. 따라서 위의 경우 방문 순서는 다음과 같습니다.

(물론 같은 level에서 무엇을 먼저 방문할지는 그래프가 표현된 방식에 따라 달라질 수 있습니다.)

u → a → b → c → d → e

 

이전에 배운 DFS와 비교해보는 것도 좋겠네요! 대략 이해가시죠? 

추가) u에서 d로 가기 위한 최단 거리는? 2

 

 

 

BFS 구현 방법 

위의 수도코드를 보면 대략 눈치를 챘을 수도 있는데, BFS를 구현하기 위해 필수인 자료구조는 뭘까요?

바로 Queue(큐) 입니다 ! 또한, BFS는 재귀적이지 않습니다. (재귀 호출이 일어나지 않습니다.)

 

먼저 들어온게 먼저 나오는 구조인 FIFO 의 특성을 지닌 Queue를 이용해서 BFS를 구현하면 됩니다!

참고로 위의 그림과 같이 동시에 저 노드들이 Queue에 존재할 일은 없긴 합니다. 저건 순서를 보여드리기 위한 그림이니, 헷갈리지 마세요! 맨 처음에 시작 노드인 u부터 맨 마지막에 들어올 노드인 e까지의 흐름도를 그려둔겁니다.

 

#include<bits/stdc++.h>
using namespace std;
//인접리스트로 그래프 구현
vector<int> adj[100];
//최단거리를 계산하기 위해 int형으로 선언
int visited[100];

int nodeList[] = { 10, 12, 14, 16, 18, 20, 22, 24 };
void BFS(int here) {
	queue<int> q;
	visited[here] = 1;
	q.push(here);
	while (q.size()) {
		int here = q.front(); q.pop();
		for (int there : adj[here]) {
			if (visited[there]) continue;
			visited[there] = visited[here] + 1; //거리 계산
			q.push(there); //방문한 노드를 q에 넣음 
		}
	}
}
int main() {
	//연결상태 표현(그래프 구현)
	adj[10].push_back(12);
	adj[10].push_back(14);
	adj[10].push_back(16);
	adj[12].push_back(18);
	adj[12].push_back(20);
	adj[20].push_back(22);
	adj[20].push_back(24);
    
    //BFS 실행(10부터)
	BFS(10);
    //모든 노드들에 대한 거리 출력
	for (int i : nodeList) {
		cout << i << " : " << visited[i] << '\n';
	}
    //시작점도 visited + 1 을 하고 시작하니까, -1을 적용해서 출력
	cout << "10번으로부터 24번까지 최단거리는 : " << visited[24] - 1 <<
		'\n';
	return 0;
}
/*

 

처음이면 조금 어려울 수 있어요. 특히 q(큐)에 넣는 부분!

BFS는 다음과 같은 흐름으로 진행됩니다. 

우선 BFS가 시작된 노드를 방문처리하고, 사용할 큐를 생성한 뒤 해당 큐 안에 시작 노드를 넣습니다.

그리고 큐에서 노드를 하나 꺼내, 해당 노드와 인접한 노드들 중 방문하지 않은 노드들을 전부 큐에 넣습니다.

이 과정을 큐가 완전히 빌 때까지 반복합니다.

 

 

사실 위의 코드는 무궁무진하게 다양화될 수 있습니다.

• 그래프의 가중치(간선의 가중치)가 한칸(1)이 아니라 두칸(2) 라면?
• 시작지점이 하나가 아니라 여러개라면?

이런 것들을 전부 고려하다보면 코드가 달라질 수 있죠.

그래프의 가중치가 2로 달라지면 visited에 더해지는 값이 달라지거나 최종 출력문에서 * 2 를 해주면 되고,

시작지점이 다수라면 처음에 bfs 함수가 받는 인자로 그만큼 늘어야하며, 처음에 큐에 푸쉬하는 노드와 방문 처리하는 노드들이 늘어날 겁니다. 

 

Q) 만약 간선마다 가중치가 다르다면요?

그땐 BFS로는 해결할 수 없습니다. 가중치가 다른 그래프 내에서의 최단거리를 구하기 위해서는

다익스트라 알고리즘, 벨만포드 알고리즘 등을 사용해야 합니다. (추후 배울 예정)

 

 

BFS 문제 예시

문제 설명

준혁이는 오늘 집에서 학교까지 가려고 합니다. 준혁이는 학교에 가장 빠르게 도착하려고 하는데, 학교로 가는 길에는 육지와 바다가 섞여 있습니다. 준혁이는 바다를 건널 수 없고, 육지만 따라가야 합니다. 준혁이는 한 칸 이동할 때마다 에너지를 소모하며, 최단 거리로 이동했을 때 얼마나 많은 에너지를 소모하는지 알고 싶습니다. 준혁이는 상하좌우로만 이동할 수 있습니다. (단, 맵의 1은 육지이며 0은 바다입니다.)

 

입력

맵의 세로 길이 N과 가로 길이 M이 주어지고, 다음 줄에 준혁이의 시작 위치 (y,x)와 학교 위치 (y,x)가 주어집니다.   그리고 마지막으로 N×M의 맵이 주어집니다. 이때 준혁이는 시작 위치에서 이미 한 번의 에너지를 소모한 상태로 간주합니다.

 

출력 

에너지를 얼마나 소모해야 하는지 출력하세요.

 

범위

1 <= N <= 100

1 <= M <= 100

 

예제 입력

5 5 0 0 4 4 1 0 1 0 1 1 1 1 0 1 0 0 1 1 1 0 0 1 1 1 0 0 1 1 1

 

예제 출력

9

 

힌트를 주자면,  "가중치가 같은 그래프 내의 최단거리 알고리즘" 문제 입니다!

BFS를 통해 최단거리 배열을 만들어서 해결해야 합니다.

 

 

정답 코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int max_n = 104, max_m = 104; //좀 더 여유롭게 설정
int N, M;
int map[max_n][max_m]; 
int visited[max_n][max_m];

//시작 위치와 끝날 위치를 담을 변수
int sy, sx;
int ey, ex;

int dy[4] = { -1, 1, 0, 0 };
int dx[4] = { 0, 0, -1, 1 };

void BFS(int y, int x) {
	visited[y][x] = 1;
	queue<pair<int, int>> q; //{y, x} pair 형식을 담아두는 q
	q.push({ y,x });
	while (!q.empty()) { //혹은 q.size()를 활용해도 됨
		pair<int, int> here = q.front(); q.pop();
		y = here.first;
		x = here.second;
		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			//범위를 벗어나거나, 갈 수 없는 곳이면 continue
			if (ny >= N || ny < 0 || nx >= M || nx < 0 || map[ny][nx] == 0 ) continue;
			if (!visited[ny][nx]) {
				visited[ny][nx] = visited[y][x] + 1;
				q.push({ ny,nx });
			}
		}
	}
	return;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> N >> M;
	cin >> sy >> sx;
	cin >> ey >> ex;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> map[i][j];
		}
	}

	BFS(sy, sx);
	//시작점에서도 에너지를 소모한다고 했으니, -1 할 필요 없음 
	cout << visited[ey][ex];

}

 

이 코드에서는 최단거리 배열의 이름은 visited 입니다!

맵의 형식이라 차원이 2차원으로 늘어났고, bfs에서 받는 인자값도 2개로 늘어났습니다.

(만약 3차원의 맵이 주어진다면, 그만큼 차원을 확장해볼 생각도 할 수 있어야 합니다!)

 

그리고 문제가 어려울 수록

도식화 → 손코딩 → 코드화 과정을 거치는 걸 추천합니다.

 

 

 

---

 

이제 DFS와 BFS를 언제 쓰면 좋을지, 간단하게 비교하고 넘어갑시다.

사실 두 방법 모두 시간 복잡도 자체는 같습니다.

 

그냥 둘의 차이점을 명확히 알아두면, 언제 사용해야할 지 감이 올겁니다.

DFS	메모리 덜 씀, 절단점을 구할 수 있음(SCC등 고급 알고리즘에 활용), 코드가 더 짧음
BFS	메모리 더 씀, 가중치가 같은 그래프 내에서 최단 거리를 구할 수 있음, 코드가 더 김

 

BFS가 메모리를 더 쓴다는 것은, 큐라는 자료구조를 필수로 사용해야하기 때문입니다.

그리고 별도의 조건 없는 완전 탐색의 경우 코드가 더 짧은 DFS를 많이들 선호합니다.

최단 거리를 구해야한다면, 무조건 BFS를 사용해야 합니다.

 

문제에서 "퍼진다" , "탐색한다" 와 같은 워딩이 보이면, DFS와 BFS 먼저 고민해봅시다 !