취미로 코딩하기

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

이번에 볼 문제는 백준 1471번 문제인 사탕 돌리기이다.
문제는 아래 링크를 확인하자.

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

주어진 문제의 상황은 functional graph로 모델링되는데, 이러한 그래프는 어느 정점에서 출발하더라도 대응되는 사이클을 끝없이 돌게 된다.

따라서 주어진 그래프에서 사이클을 모두 찾고, 각 사이클로부터 사이클에 포함되지 않는 정점까지의 거리를 구하는 것으로 문제를 해결할 수 있다.

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

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

int N;
int G[200001];
vector<int> invG[200001];
int visited[200001];
int dist[200001];
queue<int> que;
int ans;

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

	cin >> N;
	for (int i = 1; i <= N; i++) {
		int ii = i, val = 0;
		while (ii) {
			val += ii % 10;
			ii /= 10;
		}
		int nxt = i + val;
		if (nxt > N) nxt -= N;
		G[i] = nxt;
		invG[nxt].emplace_back(i);
	}
	for (int i = 1; i <= N; i++) {
		if (visited[i]) continue;
		int ii = i;
		while (!visited[ii]) {
			visited[ii] = i;
			ii = G[ii];
		}
		if (visited[ii] == i) {
			int iii = ii, cnt = 1;
			while (G[iii] != ii) {
				iii = G[iii], cnt++;
			}
			iii = ii;
			dist[iii] = cnt;
			que.push(iii);
			while (G[iii] != ii) {
				iii = G[iii];
				dist[iii] = cnt;
				que.push(iii);
			}
		}
	}
	while (!que.empty()) {
		int cur = que.front(); que.pop();
		ans = max(ans, dist[cur]);
		for (auto &x:invG[cur]) {
			if (dist[x]) continue;
			dist[x] = dist[cur] + 1;
			que.push(x);
		}
	}

	cout << ans;
}