취미로 코딩하기

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

이번에 볼 문제는 백준 24396번 문제인 푸앙이와 별이다.

문제는 아래 링크를 확인하자.

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

원본 그래프 자체를 구현하면 N이 커질 수록 시간복잡도와 공간복잡도가 O(N^2)이 되므로 문제의 제한 내로 해결하기 어렵다.

따라서, M개의 "지워진 간선"의 정보를 최대한 활용하여 그래프 위에서의 bfs를 효율적으로 해내는 방법을 생각해내야 한다. 글쓴이는 대략 아래와 같은 방법으로 문제를 해결했다.

0. 큐에 1번 노드를 집어넣는다.

1. 큐에 들어있는 노드의 개수 Q를 기록해둔다.

2. 그래프의 각 노드의 "큐에 들어있는 원소 중 안 연결된 노드"의 수를 셀 크기 N의 cnt배열을 준비하고, 그 개수를 각각 센다.

3. cnt배열을 둘러보면서, 큐에 들어있던 원소와 모두 연결되지 않은 노드(cnt==Q)가 아니라면 새로 연결되었다는 점을 이용하여 1에서부터의 거리가 확정되지 않은 점들의 거리를 채워넣는다. 이러한 노드들을 큐에 다시 채워넣고, 큐가 비어있지 않다면 1서부터 과정을 반복한다.

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

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

int N, E;
vector<int> G[300001];
int dist[300001];
int cnt[300001];

void bfs() {
	dist[1] = 1;
	int d = 2;
	queue<int> que;
	que.push(1);
	while (!que.empty()) {
		int quesize = que.size();
		memset(cnt, 0, sizeof(cnt));
		while (!que.empty()) {
			int current = que.front(); que.pop();
			for (auto node : G[current]) cnt[node]++;
		}
		for (int i = 1; i <= N; i++) {
			if (dist[i] == 0 && cnt[i] < quesize) {
				dist[i] = d;
				que.push(i);
			}
		}
		d++;
	}
}

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

	cin >> N >> E;
	while (E--) {
		int x, y; cin >> x >> y;
		G[x].emplace_back(y);
		G[y].emplace_back(x);
	}

	bfs();

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