[프로그래머스] 그래프 > 순위

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

코딩테스트 연습 - 순위

이 문제는 두가지 풀이법이 있다. 

1. 플루이드 워셜 알고리즘을 사용

2. 직관적으로 부모노드의 갯수, 자식노드의 개수를 따져서 계산 >> 이 방식으로 하다가 구현이 힘들어져서 플루이드를 사용했다.

 

일단 플루이드 워셜 방식이다.

#include <string>
#include <vector>

using namespace std;

const int INF = 987654321;
int map[101][101];

int solution(int n, vector<vector<int>> results) {
    int answer = 0;
    
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++) {
            if(i==j)
                map[i][j] = 0;
            else
                map[i][j] = INF;
        }
    
    for(int i=0; i<results.size(); i++) {
        int a = results[i][0];
        int b = results[i][1];
        map[a][b] = 1;
    }

    for(int k=1; k<=n; k++) {
        for(int a=1; a<=n; a++)
            for(int b=1; b<=n; b++) {
                map[a][b] = min(map[a][b], map[a][k] + map[k][b]);
            }
    }
    /*************** 여기까지는 일반적인 플루이드 워셜 방식이다. **********/
    
    /*************** 여기에서 고정된 순위를 확인해보자 ********/
    for(int b=1; b<=n; b++) {
        int cnt = 0;
        for(int a=1; a<=n; a++) {
            if(map[a][b] == INF) {
                if(map[b][a] != INF)
                    cnt++;
                else
                    break;
            }
            else
                cnt++;
        }
        if(cnt == n)
            answer++;

    }
    
    return answer;
}

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

플루이드 워셜 결과 나온 테이블이다.

순위가 정해져있다는 것은 모든 노드들과의 관계를 확인할 수 있다는 것을 의미한다.

따라서, 우리는 특정노드들이 본인을 제외한 노드들과의 관계를 확인할 수 있는지 확인한 후 가능하다면, answer ++ 를 해주면 된다.

 

위의 노란색은 2번 노드가 1, 2, 3, 4, 5 의 노드들 모두와 관계를 정의할 수 있다는 것을 확인하는 방식이다.

마찬가지로, 5번의 노드 같은 경우에는

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

이런식으로 확인이 가능하다.

각 노드들이 관계를 정의할 수 있는 노드의 갯수는

1 : 1개(2번)

2: 5개 (1, 3, 4, 5번)

3: 2개 (2, 4번)

4: 2개(2, 3번)

5 : 5개 (1, 2, 3, 4번)

이다.