취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 24446번 문제인 알고리즘 수업 - 너비 우선 탐색 3이다.
문제는 아래 링크를 확인하자.

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

각 노드의 BFS트리에서의 깊이, 즉 탐색 시작지점으로부터의 거리를 구하는 문제이다.

거리를 저장하는 배열을 만들고 BFS를 이용해 각 노드의 거리를 계산해 문제를 해결해주자. 이 과정에서 각 노드의 거리 대신 (거리+1)을 저장한다면 거리 배열이 visited 배열의 역할을 대신할 수 있고(값이 저장되어있으면 방문한 적이 있고, 그렇지 않다면 방문한 적이 없다) 거리 배열의 모든 값에서 1을 빼주는 것으로 모든 노드에 대해 올바른 답을 구할 수 있게 되므로 구현을 효율적으로 할 수 있다.

아래는 제출한 소스코드이다.

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

int N, M, R;
vector<int> G[100001];
int dist[100001];

void bfs() {
	queue<int> que;
	que.push(R);
	dist[R] = 1;
	while (!que.empty()) {
		int cur = que.front(); que.pop();
		for (auto& nxt : G[cur]) {
			if (dist[nxt]) continue;
			dist[nxt] = dist[cur] + 1;
			que.push(nxt);
		}
	}
}

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

	cin >> N >> M >> R;
	while (M--) {
		int u, v; cin >> u >> v;
		G[u].emplace_back(v);
		G[v].emplace_back(u);
	}

	bfs();

	for (int i = 1; i <= N; i++) cout << dist[i] - 1 << '\n';
}