취미로 코딩하기

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

이번에 볼 문제는 백준 2458번 문제인 키 순서이다.
문제는 아래 링크를 확인하자.

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

주어지는 DAG에 Floyd-Warshall 알고리즘을 사용하면, 주어진 간선을 이용해서 노드 k로 올 수 있는 노드 i의 경우 dist[i][k]값이, 노드 k에서 방문할 수 있는 노드 j의 경우 dist[k][j]값이 계산된다는 점을 이용하자.

구체적으로, 각 노드 k에 대하여 거리가 계산된 점들의 개수가 전체 노드의 개수 N개와 같다면 노드 k의 사람은 항상 다른 사람과 키를 비교할 수 있다는 뜻이 된다.

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

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

int dist[501][501];

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

	int N, M; cin >> N >> M;
	memset(dist, 0x3f, sizeof(dist));

	for (int i = 1; i <= N; i++) dist[i][i] = 0;

	while (M--) {
		int x, y; cin >> x >> y;
		dist[x][y] = 1;
	}

	for (int k = 1; k <= N; k++) {
		for (int r = 1; r <= N; r++) {
			for (int c = 1; c <= N; c++) {
				dist[r][c] = min(dist[r][c], dist[r][k] + dist[k][c]);
			}
		}
	}

	int ans = 0;

	for (int k = 1; k <= N; k++) {
		int cnt = 0;
		for (int i = 1; i <= N; i++) if (dist[i][k] < 0x3f3f3f3f || dist[k][i] < 0x3f3f3f3f) cnt++;
		if (cnt == N) ans++;
	}

	cout << ans;
}