[BOJ 23255 // C++] 구름다리 2

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

 

이번에 볼 문제는 백준 23255번 문제인 구름다리 2이다.

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

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

23255번: 구름다리 2

문제에서 주어진 조건 중, 건물의 색을 1번부터 N번까지 순서대로 나열했을 때 사전순으로 가장 앞서게 건물 외벽을 색칠하라는 조건에 주목하자.

 

사전순으로 가장 앞서는 배열을 찾을 경우, 첫 건물서부터 현재 칠할 수 있는 최대한 앞순서에 오는 색을 골라나가는 방식으로 구해나가면 된다. 최대한 앞순서에 오는 색을 고르지 않는 순간이 있다면 그 순간의 색을 더 앞순서의 색을 칠하는 것으로 항상 사전순으로 앞서는 배열을 찾아낼 수 있기 때문이다.

 

한편, 구름다리의 개수가 10만개 이하이므로 색을 가장 많이 칠하더라도 500가지보다 많은 색을 칠할 경우는 발생하지 않는다는 점을 확인하자. 사전순으로 가장 앞서는 배열을 찾는 것이므로 굳이 큰 숫자에 대응되는 색을 사용할 이유가 없고, k번 색을 색칠해야만 하는 상황은 앞선 k-1가지의 색이 칠해져있는 각각의 건물과 다리가 놓여있어야만 하는 상황이라는 것을 확인하면 500개의 색을 칠할 상황이 오려면 다리가 몇 개 필요한지 계산해볼 수 있을 것이다.

 

이를 이용하여, 1번 건물서부터 건물을 하나씩 확인하며 지금까지 칠해지지 않은 가장 작은 숫자의 색을 건물에 칠해나가는 것으로 문제를 해결할 수 있다. 전체 구름다리의 개수가 10만개이므로 "건물 확인"의 횟수는 20만회 이하일 것이고 따라서 이러한 알고리즘으로 제한시간 내로 충분히 문제를 해결할 수 있다.

 

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

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

vector<int> G[100001];
int ans[100001];
int chk[500];

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

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

	for (int i = 1; i <= N; i++) {
		memset(chk, 0, sizeof(chk));
		for (auto node : G[i]) {
			chk[ans[node]] = 1;
		}
		int idx = 1;
		while (chk[idx]) idx++;
		ans[i] = idx;
		cout << idx << ' ';
	}
}