너비 우선 탐색 (BFS) 문제 풀이

너비 우선 탐색 (BFS)

너비 우선 탐색(BFS, breadth-first search)은 그래프를 완전 탐색하는 방법 중 하나로, 시작 노드에서 출발해 시작 노드를 기준을 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘이다.

너비 우선 탐색은 선입선출 방식으로 탐색하기 때문에 큐를 이용해서 구현한다.
또한 너비 우선 탐색은 탐색 시작 노드와 가까운 노드를 우선하여 탐색하기 떄문에 목표 노드에 도착하는 경로가 여러 개일 때 최단 경로를 보장한다.

너비 우선 탐색의 특징

FIFO 탐색이다.
Queue 자료구조를 이용한다.

너비 우선 탐색의 시간 복잡도

O(V + E)

BFS의 핵심 이론

1. BFS를 시작할 때 노드를 정한 후 사용할 자료구조 초기화하기

BFS도 DFS처럼 방문한 노드는 다시 방문하지 않기 때문에 방문 배열이 필요하다. 인접 리스트로 그래프를 표현하는 것도 동일하다.
다른 점은 탐색을 할 때 스택이 아닌 큐를 활용해서 탐색한다.

2. 큐에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 큐에 삽입하기

큐에서 노드를 꺼내면서 인접 노드를 큐에 삽입한다.
이때 방문 배열을 체크해서 이미 방문한 노드는 큐에 삽입하지 않는다.
또, 큐에서 꺼낸 노드는 탐색 순서에 기록한다.

3. 큐 자료구조에 값이 없을 때까지 반복

1, 2를 큐가 빌 때까지 반복한다.

백준 1260번 DFS와 BFS

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

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

static int N;
static int M;
static int V;
static vector<vector<int>> graph;
static vector<bool> visited;
queue<int> bfsQueue;

void DFS(int v);
void BFS(int v);

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> M >> V;
	graph.resize(N + 1);

	visited = vector<bool>(N + 1, false);

	//인접 리스트 셋팅
	for (int i = 0; i < M; i++)
	{
		int a, b;
		cin >> a >> b;
		graph[a].push_back(b);
		graph[b].push_back(a);
	}
	//모든 인접 노드들을 순서에 맞게 정렬한다.
	for (int i = 0; i < N + 1; i++)
		sort(graph[i].begin(), graph[i].end());

	DFS(V);

	for (int i = 0; i < N + 1; i++)
		visited[i] = false;

	cout << endl;
	BFS(V);
	return 0;
}

void DFS(int v)
{
	if (visited[v])
		return;

	visited[v] = true;
	cout << v << " ";

	for (int i : graph[v])
	{
		if (!visited[i])
		{
			DFS(i);
		}
	}
}

void BFS(int v)
{
	if (visited[v])
		return;

	bfsQueue.push(v);
	visited[v] = true;
	cout << v << " ";

	while (!bfsQueue.empty())
	{
		int front = bfsQueue.front();
		bfsQueue.pop();

		for (int element : graph[front])
		{
			if (visited[element]) continue;
			bfsQueue.push(element);
			visited[element] = true;

			cout << element << " ";
		}
	}
}

이 문제는 단순히 DFS와 BFS를 구현할 수 있으면 풀 수 있는 문제였다!
약간 신경 쓸 것은 내림차순 순서대로 다음 노드를 선택해야 한다는 것이다.

백준 2178번 미로 탐색하기

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

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int N, M;
vector<vector<int>> visited;
vector<string> board;
queue<pair<int, int>> bfsQueue;

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

void BFS(int x, int y);

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> M;

	visited.resize(N);
	for (int i = 0; i < N; i++)
	{
		visited[i].resize(M);
		fill(visited[i].begin(), visited[i].end(), 1);
	}

	board.resize(N);

	for (int i = 0; i < N; i++)
	{
		cin >> board[i];
	}


	BFS(0, 0);

	cout << visited[N - 1][M - 1];
	return 0;
}

void BFS(int x, int y)
{
	if (visited[y][x] != 1) 
		return;

	bfsQueue.push({ x, y });

	while (!bfsQueue.empty())
	{
		auto pair = bfsQueue.front();
		bfsQueue.pop();

		//갈 수 있는 곳 탐색
		for (int i = 0; i < 4; i++)
		{
			int nextX = pair.first + dx[i];
			int nextY = pair.second + dy[i];

			//범위 체크
			if (nextX < 0 || nextX > M - 1 || nextY < 0 || nextY > N - 1)
				continue;
			//방문한 적이 있다면 스킵
			if (visited[nextY][nextX] != 1)
				continue;
			if (board[nextY][nextX] == '0')
				continue;
			
			visited[nextY][nextX] = visited[pair.second][pair.first] + 1;
			bfsQueue.push({ nextX, nextY });
		}
	}
}

이제 미로가 나오고 최단 거리를 구하는 문제이기 때문에 BFS가 먼저 떠올랐다. DFS보다 BFS가 적합한 이유는 BFS는 해당 깊이에서 가능한 모든 노드 탐색을 마친 후 다음 깊이로 넘어가기 때문이다.

무난하게 BFS 알고리즘을 써서 방문 조건과 인덱스 조건을 잘 걸러내서 답을 구할 수 있었다.
과거에 풀었던 내용을 보니까. 지금 풀이처럼 동적으로 자료구조의 크기를 입력 값에 따라서 넣는 것이 아니라. 그냥 전역에 가능한 최대의 수치로 자료구조 크기를 확보하는 방법도 있었다. 메모리가 부족하지 않다면 활용하는 것이 좋아보였다.

백준 1167번 트리의 지름 구하기

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

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int V;

vector<vector<pair<int, int>>> graph;
void bfs(int start);
vector<int> dist;
queue<int> bfsQueue;
vector<bool> visited;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	cin >> V;
	graph.resize(V + 1);
	dist.resize(V + 1, 0);
	visited.resize(V + 1, false);

	for (int i = 0; i < V; i++)
	{
		int v;
		cin >> v;
		while (true)
		{
			int node;
			cin >> node;
			if (node == -1)
				break;

			int weight;
			cin >> weight;
			graph[v].push_back({ node, weight });
		}
	}

	// 임의의 노드 하나를 잡고 bfs를 수행한 후 최장 거리의 노드를 구한다.
	bfs(1);

	pair<int, int> maxNode = { 0, 0 };
	for (int i = 0; i < dist.size(); i++)
	{
		if (maxNode.second < dist[i])
		{
			maxNode.second = dist[i];
			maxNode.first = i;
		}
	}

	fill(dist.begin(), dist.end(), 0);
	fill(visited.begin(), visited.end(), false);

	// 그 노드에서 다시 최장 거리를 구하면 그게 트리의 지름이다.
	bfs(maxNode.first);
	pair<int, int> answerNode = { 0, 0 };
	for (int i = 0; i < dist.size(); i++)
	{
		if (answerNode.second < dist[i])
		{
			answerNode.second = dist[i];
			answerNode.first = i;
		}
	}
	cout << answerNode.second;

	return 0;
}

void bfs(int start)
{
	bfsQueue.push(start);

	while (!bfsQueue.empty())
	{
		int node = bfsQueue.front();
		bfsQueue.pop();

		visited[node] = true;

		for (int i = 0; i < graph[node].size(); i++)
		{
			if (visited[graph[node][i].first] == true)
				continue;
			//거리 업데이트
			dist[graph[node][i].first] = dist[node] + graph[node][i].second;
			bfsQueue.push(graph[node][i].first);
		}
	}
}

이 문제를 풀기 위해서는 트리에 대한 이해가 있어야 한다.
트리는 모든 노드가 서로 유일한 경로로 연결이 되어 있고, 싸이클이 존재하지 않는 그래프이다.
트리의 지름을 구하기 위해서는 이 아이디어가 있어야 한다.
아이디어가 가장 중요했던 문제이다.

임의의 노드에서 가장 긴 경로로 연결된 노드는 트리의 지름에 해당하는 두 노드 중 하나이다.

임의의 A 노드에서 가장 멀리 있는 B노드는 트리의 지름의 양 끝 노드 중 하나라는 의미이다.

그 아이디어만 잘 염두해두면 로직은 간단하다.

공부 자료 : Do it! 알고리즘 코딩 테스트 C++ (김종관, 이지스퍼블리싱)