취미로 코딩하기

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

이번에 볼 문제는 백준 14953번 문제인 Game Map이다.
문제는 아래 링크를 확인하자.

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

더 작은 차수의 노드에서 더 큰 차수의 노드로만 이동이 가능하므로, 주어진 그래프에서의 이동 가능한 관계를 그래프로 나타내면 이는 DAG를 이룸을 알 수 있다.

따라서 주어진 문제는 DAG에서의 최장거리를 구하는 문제로 볼 수 있고, 이는 위상정렬을 통해 쉽게 해결할 수 있다. 이를 구현해 문제를 해결하자.

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

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

int N, K;
vector<int> G[100000];
int deg[100000], idg[100000];
int dist[100000], mx;
vector<pair<int, int>> E;
queue<int> que;
void bfs() {
	while (!que.empty()) {
		int cur = que.front(); que.pop();
		mx = max(mx, dist[cur]);
		for (auto &nxt : G[cur]) {
			idg[nxt]--;
			dist[nxt] = max(dist[nxt], dist[cur] + 1);
			if (!idg[nxt]) que.push(nxt);
		}
	}
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> K;
	while (K--) {
		int x, y; cin >> x >> y;
		E.emplace_back(make_pair(x, y));
		deg[x]++, deg[y]++;
	}

	for (auto &p : E) {
		if (deg[p.first] > deg[p.second]) G[p.second].emplace_back(p.first), idg[p.first]++;
		else if (deg[p.first] < deg[p.second]) G[p.first].emplace_back(p.second), idg[p.second]++;
	}
	for (int i = 0; i < N; i++) {
		if (!idg[i]) {
			que.push(i);
			dist[i] = 1;
		}
	}
	bfs();
	cout << mx;
}