백준 2458번 키 순서

< 백준 2458번 키 순서 - 마포 코딩박 >

사용한 알고리즘: 플로이드 와샬


 학생들의 키 결과가 입력으로 주어졌을 때, 자신의 키가 몇번째인지 아는 학생 수를 구하는 문제였습니다.
 자신을 제외한 모든 학생에 대해, 자신에서 학생으로 갈 수 있거나, 학생에서 자신으로 올 수 있으면 자신이 몇번째인지 알 수 있습니다.
 따라서 플로이드 와샬을 통해 각 학생들간의 거리를 구하고, 자신을 제외한 모든 학생에 대한 거리가 있는 경우를 찾았습니다.

풀이는 다음과 같습니다.

(1) 모든 학생들 간의 거리는 초기값을 Infimum으로 설정해 둡니다. ( 플로이드 와샬을 구현하기 위해 )

(2) 입력으로 주어지는 학생 a,b 사이의 거리를 저장합니다. ( 거리를 1 로 생각했습니다. )

(3) 플로이드 와샬 (for 구문 3번) 을 통해 모든 학생들 사이에 존재하는 거리를 구합니다.

(4) 각 학생들이 아는 키의 경로 (거리가 Infimum 보다 작은 경우) 를 구할겁니다.

(5) 학생 i - > j 의 거리가 Infimum 보다 작은 경우 ( 경로가 존재하는 경우 ) i 가 아는 학생수 ++ , j 가 아는 학생수 ++ 을 해줍니다.

(6) 학생수가 N-1 (자신을 제외한 전체) 인 학생인 경우가 구하고자하는 학생(수) 입니다.

처음 말씀드린 생각 ( 모든 경로를 아는 학생이 답이다 ) 를 생각하고,
플로이드 와샬을 구현하는 문제였습니다. 해보지는 않았지만, 다익스트라나 벨만 포드를 써도 상관 없을 것 같습니다.

	#include <bits/stdc++.h>
	using namespace std;
	const int INF = 1<<20;
	const int MAX = 501;
	int N, M, ans, dist[MAX][MAX], path[MAX];
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin >> N >> M;
	for (int i = 0; i < N; ++i)
	for (int j = 0; j < N; ++j)
	dist[i][j] = i==j? 0:INF;
	for (int i = 0; i < M; ++i){
	int a, b;
	cin >> a >> b;
	dist[a-1][b-1] = 1;
	}
	//플로이드 와샬로 각 점에서 다른 점으로 갈 수 있는 길 확인
	for (int k = 0; k < N; ++k)
	for (int i = 0; i < N; ++i)
	for (int j = 0; j < N; ++j)
	dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j]);
	for (int i = 0; i < N; ++i){
	for (int j = 0; j < N; ++j){
	if(i==j) continue;
	// i -> j 갈 수 있으면 i,j 점이 각각 아는 학생수 +1
	if(dist[i][j]<INF){
	path[i]++;
	path[j]++;
	// 자신을 제외한 모든 점으로 갈 수 있으면 정답
	if(path[i]==N-1)ans++;
	if(path[j]==N-1)ans++;
	}
	}
	}
	cout << ans << '\n';
	return 0;
	}

view raw BOJ 2458.cpp hosted with ❤ by GitHub