[G5] 백준 14217번 그래프 탐색 C++ 너비 우선 탐색, unordered_set

리뷰

 

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

그냥 BFS를 q번 돌렸더니 시간이 어마어마하게 나왔다.

 

 

전역 변수

• N : 배열의 최대 크기를 정의할 상수 변수
• n : 정점의 개수를 저장할 변수
• m : 간선의 개수를 저장할 변수
• edges : 인접 리스트를 저장할 정수타입 unordered_set 배열
• Pos : 현재 노드 번호와 누적 거리를 정의할 구조체

 

함수

1. bfs

void bfs() {
	queue<Pos> ps;
	ps.push({ 1, 0 });
	vector<int> dist(n + 1, -1);
	dist[1] = 0;

	while (!ps.empty()) {
		auto [cn, ct] = ps.front(); ps.pop();

		for (int nn : edges[cn]) {
			if (dist[nn] != -1) continue;
			dist[nn] = ct + 1;
			ps.push({ nn, ct + 1 });
		}
	}

	for (int i = 1; i <= n; ++i) {
		cout << dist[i] << (i != n ? " " : "");
	}
	cout << "\n";
}

 

1번 노드에서 모든 노드까지의 거리를 구하고 출력하기 위한 함수

 

 

문제풀이

1. n, m값을 입력 받고, m개의 간선 정보를 입력 받아 edges를 초기화한다.
2. q값을 입력 받고, q번의 쿼리 정보를 입력 받아 edges를 초기화 하고, bfs함수를 호출한다.
3. bfs함수 내부에선 1번 노드에서 모든 노드까지의 거리를 정수형 벡터 dist에 저장한다.
4. 1~n번 노드를 순회하며 dist값을 출력 후 개행문자를 삽입하여 줄 바꿈을 수행한다.

 

트러블 슈팅

없음

 

 

참고 사항

1. 각 쿼리마다 n번 노드까지의 거리를 출력 후 줄바꿈을 수행해 주면 WA를 받는 듯 하다.
2. 따라서 마지막 노드까지의 거리를 출력 후엔 공백을 삽입하지 않았다.

 

정답 코드

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

const int N = 501;
int n, m, q;
unordered_set<int> edges[N];
struct Pos {
	int cn, ct;
};

void bfs() {
	queue<Pos> ps;
	ps.push({ 1, 0 });
	vector<int> dist(n + 1, -1);
	dist[1] = 0;

	while (!ps.empty()) {
		auto [cn, ct] = ps.front(); ps.pop();

		for (int nn : edges[cn]) {
			if (dist[nn] != -1) continue;
			dist[nn] = ct + 1;
			ps.push({ nn, ct + 1 });
		}
	}

	for (int i = 1; i <= n; ++i) {
		cout << dist[i] << (i != n ? " " : "");
	}
	cout << "\n";
}

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

	cin >> n >> m;
	while (m--) {
		int f, ct; cin >> f >> ct;
		edges[f].insert(ct);
		edges[ct].insert(f);
	}

	cin >> q;
	while (q--) {
		int o, f, ct; cin >> o >> f >> ct;
		if (o == 1) {
			edges[f].insert(ct);
			edges[ct].insert(f);
		}
		else {
			edges[f].erase(ct);
			edges[ct].erase(f);
		}

		bfs();
	}
}