프로그래머스 순위

모든 정점에 대해서 연결 유무를 파악해야 하는 플로이드 와샬 알고리즘 문제다. 최단 경로보다는 연결 유무에 초점이 맞춰져있는 문제다. 하나의 노드에 관해서 나가는 간선과 들어오는 간선의 합이 반드시 N-1이어야만 확실한 순위를 알 수 있다

 

문제: https://programmers.co.kr/learn/courses/30/lessons/49191

깃허브주소: https://github.com/surinoel/boj/blob/master/Programmers_순위.cpp

 

	#include <string>
	#include <vector>
	#include <algorithm>
	using namespace std;
	int d[101][101];
	int solution(int n, vector<vector<int>> results) {
	int answer = 0;
	fill(&d[0][0], &d[n][n + 1], 1e6);
	for (int i = 0; i < results.size(); i++) {
	int x = results[i][0];
	int y = results[i][1];
	d[x][y] = 1;
	}
	for (int k = 1; k <= n; k++) {
	for (int i = 1; i <= n; i++) {
	for (int j = 1; j <= n; j++) {
	if (d[i][j] > d[i][k] + d[k][j]) {
	d[i][j] = d[i][k] + d[k][j];
	}
	}
	}
	}
	for (int i = 1; i <= n; i++) {
	bool ok = true;
	for (int j = 1; j <= n; j++) {
	if (i == j) continue;
	if (d[i][j] == 1e6 && d[j][i] == 1e6) {
	ok = false;
	break;
	}
	}
	if (ok) answer += 1;
	}
	return answer;
	}

view raw Programmers_순위.cpp hosted with ❤ by GitHub