[Do it! 알고리즘 코딩테스트: Chapter 5] 너비 우선 탐색(Breadth-First Search)

본 포스팅은 Do it! 알고리즘 코딩테스트: C++편을 토대로 공부한 내용을 정리하기 위한 포스팅입니다.

https://github.com/KwonKiHyeok/Do_it_Alogrithm_Coding_Test_with_Cpp

GitHub - KwonKiHyeok/Do_it_Alogrithm_Coding_Test_with_Cpp: Do it! 알고리즘 코딩 테스트: C++편

 

너비 우선 탐색(Breadth-First Search)

 

 너비 우선 탐색(Breadth-First Search, BFS)은 그래프나 트리와 같은 자료구조에서 루트 노드(또는 시작 노드)부터 시작하여 인접한 노드들을 먼저 방문한 후, 그 다음 레벨의 노드들을 방문하는 탐색 방법이다.

 

BFS의 핵심 아이디어

• 레벨별 탐색: 시작 노드에서부터 인접한 노드들을 모두 방문한 후, 그 다음 인접 노드들(한 단계 더 떨어진 노드)을 방문한다.
• 큐(Queue)를 사용: 탐색 순서를 유지하기 위해 선입선출(FIFO) 방식의 큐를 활용한다.
• 최단 경로 탐색: 가중치가 없는 그래프에서 시작 노드로부터 다른 노드까지의 최단 경로(최소 간선 수)를 찾는 데 유용하다.

 

BFS 알고리즘 단계

1. 시작 노드 설정 및 초기화:
   • 시작 노드를 큐에 넣고, 방문 표시(visited)를 한다.
2. 반복 탐색:
   • 큐가 비어 있지 않은 동안 다음을 반복한다:
     1. 큐의 맨 앞에 있는 노드를 꺼낸다.
     2. 해당 노드에 인접한 모든 노드를 확인한다.
     3. 방문하지 않은 노드라면 방문 표시를 하고 큐에 넣는다.
3. 종료:
   • 큐가 비면 모든 노드를 방문한 것으로 탐색을 종료한다.

 

// Baekjoon Online Judge Problem. 1260

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

void DFS(vector<vector<int>>& graph, vector<bool>& visited, int node);
void BFS(vector<vector<int>>& graph, vector<bool>& visited, int node);

int main() {
	int N, M, V;

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

	cin >> N >> M >> V;
	vector<vector<int>> graph(N + 1);
	vector<bool> visited1(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(graph, visited1, V);
	cout << '\n';

	vector<bool> visited2(N + 1, false);
	BFS(graph, visited2, V);

	return 0;
}

void DFS(vector<vector<int>>& graph, vector<bool>& visited, int node) {
	
	cout << node << ' ';
	visited[node] = true;

	for (int i : graph[node]) {
		if (visited[i] == false) {
			DFS(graph, visited, i);
		}
	}
	return;
}

void BFS(vector<vector<int>>& graph, vector<bool>& visited, int node) {
	
	queue<int> q;
	q.push(node);

	while (q.empty() != true) {
		int next = q.front();
		visited[next] = true; q.pop();
		cout << next << ' ';

		for (int i : graph[next]) {
			if (visited[i] == false) {
				q.push(i);
				visited[i] = true;
			}
		}
	}
	return;
}

 

 

// Baekjoon Online Judge Problem. 2178

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

void BFS(vector<vector<int>>& matrix, vector<vector<int>>& visited, pair<int, int> node);
int answer;

int main() {
	int N, M;

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

	cin >> N >> M;
	vector<vector<int>> matrix(N, vector<int>(M, 0));
	vector<vector<int>> visited(N, vector<int>(M, -1));

	for (int i = 0; i < N; i++) {
		string row;
		cin >> row;
		for (int j = 0; j < M; j++) {
			matrix[i][j] = row[j] - '0';
		}
	}
	
	BFS(matrix, visited, { 0, 0 });

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

void BFS(vector<vector<int>>& matrix, vector<vector<int>>& visited, pair<int, int> node) {
	
	int y = node.first, x = node.second;
	int dx[4] = { 1, 0, -1, 0 };
	int dy[4] = { 0, 1, 0, -1 };

	queue<pair<int, int>> q;
	q.push({ x, y });
	visited[y][x] = 1;

	while (!q.empty()) {
		pair<int, int> cur = q.front(); q.pop();

		for (int i = 0; i < 4; i++) {
			int n_x = cur.first + dx[i];
			int n_y = cur.second + dy[i];

			if (-1 < n_y && n_y < visited.size() && -1 < n_x && n_x < visited[0].size()) {
				if (visited[n_y][n_x] == -1 && matrix[n_y][n_x] == 1) {
					visited[n_y][n_x] = visited[cur.second][cur.first] + 1;
					q.push({ n_x, n_y });
				}
			}
			else continue;
		}
	}
}

 

 

// Baekjoon Online Judge Problem. 1167

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

void BFS(vector<vector<pair<int, int>>>& tree, vector<bool>& visited, int node, vector<int>& length);
int answer;

int main() {
	int V;

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> V;
	vector<bool> visited(V + 1, false);
	vector<int> length(V + 1, 0);
	vector<vector<pair<int, int>>> tree(V + 1); // Change to vector of vector of pairs

	for (int i = 1; i <= V; i++) {
		int node;
		cin >> node;
		while (true) {
			int a, b;
			cin >> a;

			if (a == -1) break;
			cin >> b;
			tree[node].push_back(pair<int, int>(a, b));
		}
	}


	BFS(tree, visited, 1, length);

	int maxi = -1, index = -1;

	for (int i = 1; i <= V; i++) {
		if (maxi < length[i]) {
			maxi = length[i];
			index = i;
		}
	}

	visited = vector<bool>(V + 1, false);
	length = vector<int>(V + 1, -1);

	BFS(tree, visited, index, length);

	maxi = -1;
	for (int i = 1; i <= V; i++) {
		if (maxi < length[i]) {
			maxi = length[i];
		}
	}
	cout << maxi;
	return 0;
}

void BFS(vector<vector<pair<int, int>>>& tree, vector<bool>& visited, int node, vector<int>& length) {

	visited[node] = true;
	length[node] = 0;
	queue<pair<int, int>> q;
	q.push({ node, 0 });

	while (!q.empty()) {
		pair<int, int> cur = q.front(); q.pop();
		visited[cur.first] = true;

		for (pair<int, int> i : tree[cur.first]) {

			if (visited[i.first] == false) {
				length[i.first] = length[cur.first] + i.second;
				q.push(i);
			}
		}
	}
}

 

 이 문제는 임의의 노드에서 가장 긴 경로로 연결된 노드는 트리의 지름에 해당하는 두 노드 중 하나라는 사실을 깨닫는 것이다. 따라서 아무 노드에서 한번 시작하여 트리의 지름에 해당하는 노드 하나를 찾고, 그 다음에 BFS를 한번 더 시행해 나머지 노드를 찾으면 해결할 수 있는 문제였다.

 또 문제의 특이한 점은 queue에 pair<int, int> 형태를 넣는다는 점이 지금까지의 BFS 문제들과 달랐다.