[프로그래머스]level-3 순위 (플로이드 와샬 알고리즘)

순위 풀러가기

프로그래머스에서 순위 라는 문제를 만났음

플로이드 와샬 알고리즘을 이용하는 문제라고함

플로이드 와샬이 뭔지 알아보고 풀어보기~!

나동빈님의 알고리즘 영상

• 다익스트라알고리즘 : 하나의 정점에서 모든 정점으로 가는 최단경로

• 플로이드와샬 : 모든 정점에서 모든 정점으로 가는 최단경로

  • 2차원 배열로 값이 저장된다고 생각(다익스트라는 1차원)
  • x->y 가는 비용 vs x -> node1 + node1 -> y 합산 비교해서 적은 값 갱신

  

 #include <string>
 #include <vector>

using namespace std;

int number = 4;
int INF = 100000000;

//자료 배열 초기화 ( i > j 거리)
int a[4][4] = {
    {0, 5, INF, 8},
    {7, 0, 9, INF},
    {2, INF, 0, 4},
    {INF, INF, 3, 0}
};

void floydWarchall() {
    //결과 그래프 초기화
    int d[number][number];
    
    for(int i = 0; i < number; i++) {
        for (int j = 0; j < number; j++) {
            d[i][j] = a[i][j];
        }
    }
    
    //3중포문으로 구현
    //k = 거쳐가는 노드
    for (int k = 0; k < number; k++) {
        //i는 출발노드
        for (int i = 0; i < number; i++) {
            //j는 도착노드
            for (int j = 0; j < number; j++) {
                // 갱신
                if (d[i][k] + d[k][j] < d[i][j]) {
                    d[i][j] = d[i][k] + d[k][j];
                }
            }
        }
    }
}

---

이제 프로그래머스 문제에 적용 시켜보자

일단ㄴ

1~5번 노드까지 있다고 보고 자료배열을 만들어보자

• 총 100명 까지 선수가 있을 수 있음
• 승/패 이기 때문에 boolean 배열로 만듦

bool a[101][101];

int solution(int n, vector<vector<int>> results) {
    int answer = 0;
    
    for (int i = 0; i < results.size(); i++) {
        int x = result[i][0];
        int y = result[i][1];
        //x 가 y를 이김
        a[x][y] = true;
    }
    
    return answer;
}

일단 배운걸 그대로 적용해보면

for(int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (a[i][k] && a[k][j]) {
                    //a[i][j] = a[i][k] + a[k][j];
                    a[i][j] = true;
                }
            }
        }
    }

이러한 3중 반복문이 나온다

이제 정답을 찾을 논리를 떠올려보면

a 가 b 를 이기고 b 가 c 를 이겻으면 a 가 c 를 이긴거라 볼수 있고
저 삼중포문을 돌고나면
각 선수마다 나머지 네 선수에게까지 승패여부가 닿는지를 알 수 있을거다
그러면 자신을 제외한 n-1 번의 승패여부가 영향이 닿는지를 체크하면될 거 같다.

이문제에 적용시킬 때는 최솟값을 계산하여 갱신 시키기 보다 건너건너거 영향력이 닿는지 참/거짓 값을 대입하고 + 추가로 인당 n-1의 결과를 갖고 있게 되어야 한다는 것을 파악해야하는 문제였다.

승 / 패 가 중요하지않다 승패 여부의 영향력이 닿아있어야 한다.

• 전체 코드

#include <string>
#include <vector>

using namespace std;

bool a[101][101];

int solution(int n, vector<vector<int>> results) {
    int answer = 0;
    
    for (int i = 0; i < results.size(); i++) {
        int x = results[i][0];
        int y = results[i][1];
        //x 가 y를 이김
        a[x][y] = true;
    }
    
    for(int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (a[i][k] && a[k][j]) {
                    //a[i][j] = a[i][k] + a[k][j];
                    a[i][j] = true;
                }
            }
        }
    }
    
    for (int i = 1; i <= n; i++) {
        int count = 0;
        for (int j = 1; j <= n; j++) {
            if (a[i][j] || a[j][i]) count++;
        }
        
        if (count == n - 1) answer++;
    }
    
    
    return answer;
}