[C++] 백준 2458 : 키 순서

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

2458번: 키 순서

백준 2458번 키 순서를 풀었다.

 

먼저 플로이드 와샬 알고리즘으로 전체 노드의 비용을 구한다.

예제 1을 인풋으로 넣었을 때 dist배열이다.

	1	2	3	4	5	6
1	0	2	INF	2	1	3
2	INF	0	INF	INF	INF	INF
3	INF	2	0	1	INF	2
4	INF	1	INF	0	INF	1
5	INF	1	INF	1	0	2
6	INF	INF	INF	INF	INF	0

 

그 다음 알아볼 노드 i 에 대해서 j 로 가는 경로가 없을 경우 j 를 벡터 v 에 넣는다.

예제에서 4번 노드의 경우 1, 3, 5번 노드로 가는 경로가 없기 때문에 벡터 v에 1, 3, 5 를 넣는다.

2, 4번 노드로 가는 비용이 있기 때문에 2, 4번과는 키를 비교할 수 있다. 따라서 1, 3, 5번 노드와 키를 비교할 수 있다면 4번 노드는 자신의 키가 몇 번째인지 알 수 있다.

 

벡터 v 에 넣어진 j 값들을 하나씩 빼서 j 에서 i 로 가는 경로가 있다면 flag를 1로 유지하고 없다면 flag를 0으로 갱신한다.

벡터를 비울 때 까지 flag가 1로 유지된다면 i 노드는 자신의 키가 몇 번째인지 알 수 있다.

예제의 경우를 살펴보자. 벡터 v에는 1, 3, 5 가 들어있고 하나씩 꺼내서 알아봐야 한다.

1번 노드에서 4번 노드로 가는 비용이 2므로 경로가 있고, 키를 비교할 수 있다.

3번 노드에서 4번 노드로 가는 비용이 1이므로 경로가 있고, 키를 비교할 수 있다.

5번 노드에서 4번 노드로 가는 비용이 1이므로 경로가 있고, 키를 비교할 수 있다.

벡터에 있는 모든 노드들이 4번 노드로 가는 경로가 있으므로 flag는 1로 유지되고 4번 노드는 자신의 키가 몇 번째인지 알 수 있다.

 

 

아래는 전체 코드입니다.

#include <iostream>
#include <stdio.h>
#include <string>
#include <algorithm>
#include <vector>
#pragma warning(disable:4996)
using namespace std;

#define INF 10000000

int adj[501][501];
int dist[501][501];


int main() {
	int n, m;

	cin >> n >> m;

	for (int i = 0; i < m; i++) {
		int small, tall;
		//cin >> small >> tall;
		scanf("%d %d", &small, &tall);
		adj[small][tall] = 1;
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (i == j)
				dist[i][j] = 0;
			else if (adj[i][j] != 0)
				dist[i][j] = adj[i][j];
			else
				dist[i][j] = INF;
		}
	}

	for (int k = 1; k <= n; k++) { // Via node
		for (int i = 1; i <= n; i++) { // Start node
			for (int j = 1; j <= n; j++) { // End node
				dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
			}
		}
	}

	int cnt = 0;
	vector<int> v;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (dist[i][j] == INF)
				v.push_back(j);
		}

		int flag = 1;
		while (!v.empty()) {
			int check = v.back();
			v.pop_back();
			if (dist[check][i] == INF)
				flag = 0;
		}

		if (flag)
			cnt++;
	}

	cout << cnt;

	return 0;
}