알고리즘(C++) / 프로그래머스 level 3 : 순위

알고리즘(C++) / 프로그래머스 level 3 : 순위

level 3 : 순위

https://programmers.co.kr/learn/courses/30/lessons/49191?language=cpp

코드

//프로그래머스 순위 #include #include #include using namespace std; int solution(int n, vector> results) { int answer = 0; int graph[101][101] = { false, }; for (int i = 0; i < results.size(); i++) { graph[results[i][0]][results[i][1]] = 1; // graph 생성 } //floyd warshall for (int k = 1; k <= n; k++) { for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (graph[i][k] && graph[k][j]) { graph[i][j] = 1; } } } } for (int i = 1; i <= n; i++) { int count = 0; for (int j = 1; j <= n; j++) { if (graph[i][j] || graph[j][i]) { //graph[i][j] : win, graph[j][i] : lose count++; } } if (count == n - 1) { //자기 자신을 제외한 모든 사람의 우위를 가릴 수 있음 answer++; } } return answer; } int main() { int n = 5; vector> results = { {4,3}, {4,2}, {3,2}, {1,2}, {2,5} }; cout << solution(n, results) << "

"; return 0; }

설명

이차원 배원 graph를 생성해서 어떤 선수를 이겼는지 배열에 저장한다.

floyd warshall를 사용하여 모든 선수에 대해 이겼으면 1을 배열에 저장한다.

floyd warshall은 가중 그래프에서 최단 경로들을 찾는 알고리즘이다. 모든 노드 간의 최단 경로의 길이를 찾을 수 있다.

1번부터 n번까지 우위를 가릴 수 있는 사람이 본인을 제외한 전부라면 정확하게 순위를 매길 수 있다.

고찰

그래프 문제는 쉽게 풀 수 있을 줄 알았지만 그렇지 않았다. 어떻게해야 정확하게 순위를 매길 수 있는 사람의 수를 구할 수 있을지 생각하지 못해서 결국 구글링의 도움으로 문제를 풀 수 있었다.

floyd 알고리즘은 알고는 있었지만 이런 문제에 적용하려니 막막했다...

from http://se-jung-h.tistory.com/132 by ccl(A) rewrite - 2021-08-09 13:27:10