[프로그래머스]그래프 : 순위 (level 3)(c++)

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

코딩테스트 연습 - 순위

 

 

* Floyd-Warshall 알고리즘 활용

방법 1: 상태를 3가지로 나누기 - LOSE, UNKNOWN, WIN 

#include <string>
#include <vector>

using namespace std;

enum { LOSE = -1, UNKNOWN, WIN };

int solution(int n, vector<vector<int>> results) {

    /*
        Floyd-Warshall 알고리즘 활용
    */

    // 승패결과 n * n테이블 만들기
    vector<vector<int>> table(n, vector<int>(n, UNKNOWN));
    for (int i = 0; i < results.size(); ++i)
    {
        int winner = results[i][0] - 1;
        int loser = results[i][1] - 1;

        table[winner][loser] = WIN;
        table[loser][winner] = LOSE;
    }

    /*
        [from vs to] 결과가 불확실 한 경우
        : [from vs k], [k vs to] 로 확실한 승패를 추론해서 기록
    */
    for (int k = 0; k < n; ++k)
    {
        for (int from = 0; from < n; ++from)
        {
            // [from vs k]결과가 확실하지 않으면
            if (table[from][k] == UNKNOWN)
            {
                continue;
            }

            for (int to = 0; to < n; ++to)
            {
                // [k vs to]결과가 확실하지 않으면
                if (table[k][to] == UNKNOWN)
                {
                    continue;
                }

                /*
                    [from vs to] 우승 : [from vs k], [k vs to] 모두 우승
                    [from vs to] 패배 : [from vs k], [k vs to] 모두 패배
                */
                if (table[from][k] == table[k][to])
                {
                    table[from][to] = table[from][k];
                }
            }
        }
    }

    int certain_cnt = n;
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            if (i == j)
            {
                continue;
            }

            /*
                확실하지 않은 승패가 있다면 
                순위가 확정되지 않은 것이므로 certain_cnt - 1
            */
            if (table[i][j] == UNKNOWN)
            {
                --certain_cnt;
                break;
            }
        }
    }
    return certain_cnt;
}

 

 

방법 2: 상태를 2가지로 나누기 - (LOSE, WIN)

#include <string>
#include <vector>

using namespace std;

enum {LOSE, WIN};

int solution(int n, vector<vector<int>> results) {


    /*
        Floyd-Warshall 알고리즘 활용
    */

    // 승패결과 n * n테이블 만들기
    vector<vector<bool>> table(n, vector<bool>(n, LOSE));
    for (int i = 0; i < results.size(); ++i)
    {
        int winner = results[i][0] - 1;
        int loser = results[i][1] - 1;

        table[winner][loser] = WIN;
    }

    /*
         [from vs to] 결과가 불확실 한 경우
         : [from vs k], [k vs to] 로 확실한 승패를 추론해서 기록
     */
    for (int k = 0; k < n; ++k)
    {
        for (int from = 0; from < n; ++from)
        {
            if (table[from][k] == LOSE)
            {
                continue;
            }

            for (int to = 0; to < n; ++to)
            {
                if (table[k][to] == LOSE)
                {
                    continue;
                }

                /*
                    [from vs to] 우승 : [from vs k], [k vs to] 모두 우승
                    ([from vs to] 패배 : 이미 LOSE로 세팅되어 있다)
                */
                table[from][to] = WIN;
            }
        }
    }

    int certain_cnt = 0;
    for (int A = 0; A < n; ++A)
    {
        int cnt = 0;
        for (int B = 0; B < n; ++B)
        {
            // A vs B 둘중 하나가 이겼다면 두 선수의 승패는 확실하다
            if (table[A][B] == WIN || table[B][A] == WIN)
            {
                ++cnt;
            }
        }
        /*
            자기자신을 제외한 나머지 선수와의 승패가 모두 확실하다면
            순위가 확실하므로 certain_cnt + 1
        */
        if (cnt == n - 1)
        {
            ++certain_cnt;
        }
    }
    return certain_cnt;
}

 

 

 

** 방법 1 설명 **

권투 경기는 1대1 방식으로 진행이 되고,
만약 A 선수가 B 선수보다 실력이 좋다면 A 선수는 B 선수를 항상 이깁니다.
심판은 주어진 경기 결과를 가지고 선수들의 순위를 매기려 합니다.
하지만 몇몇 경기 결과를 분실하여 정확하게 순위를 매길 수 없습니다.

- 선수의 수는 1명 이상 100명 이하입니다.
- 경기 결과는 1개 이상 4,500개 이하입니다.

 

선수를 노드, 경기 결과를 간선이라고 한다면 위 문제의 주요 특징은 다음과 같다.

 

1. 노드 개수가 적다. 

2. 노드 A와 B의 관계를 제 3의 노드 K를 통해 유추해야 한다.

3. 다른 모든 노드들과의 관계가 확실해진 노드만 카운팅 해야 한다.

따라서 플로이드-와샬 Floyd-Warshall 알고리즘이 적절하다!

 

 

플로이드-와샬 알고리즘(이하 플로이드)은 

원래 모든 정점에서 모든 정점으로의 최단경로를 구하는 데에 쓰여진다.

하지만 이 문제는 최단 경로를 구하는 것이 목적이 아니라,

두 노드 사이의 승패 관계만 정하면 되기 때문에 플로이드를 살짝 변형해서 쓴다. 

 

 

예를 들면

table[A][K] = WIN, table[K][B] = WIN 일 때, table[A][B] = WIN 

table[A][K] = LOSE, table[K][B] = LOSE 일 때, table[A][B] = LOSE 이다.

하지만 table[A][K] = WIN, table[K][B] =LOSE 일 때는 table[A][B] =??? 알 수가 없다. 

 

따라서 table[A][K] 와 table[K][B] 가 동일할 때에만 table[A][B]의 결과를 확실하게 알 수 있다.

/*
    [from vs to] 결과가 불확실 한 경우
    : [from vs k], [k vs to] 로 확실한 승패를 추론해서 기록
*/
for (int k = 0; k < n; ++k)
{
    for (int from = 0; from < n; ++from)
    {
        for (int to = 0; to < n; ++to)
        {
            /*
                [from vs to] 우승 : [from vs k], [k vs to] 모두 우승
                [from vs to] 패배 : [from vs k], [k vs to] 모두 패배
            */
            if (table[from][k] == table[k][to])
            {
                table[from][to] = table[from][k];
            }
        }
    }
}

 

 

이후 다른 노드들의 승패관계가 명확하게 정해진 노드의 개수만 구해주면 된다.

int certain_cnt = n;
for (int i = 0; i < n; ++i)
{
    for (int j = 0; j < n; ++j)
    {
        if (i == j) continue;
        /*
            확실하지 않은 승패가 있다면 
            순위가 확정되지 않은 것이므로 certain_cnt - 1
        */
        if (table[i][j] == UNKNOWN)
        {
            --certain_cnt;
            break;
        }
    }
}
return certain_cnt;

 

 

 

** 방법 2 설명 **

위의 풀이에서 더 나아가서,

노드간의 관계가 승(1) 패(0) 로만 나뉜다는 점을 이용할 수 있다.

 

UNKNOWN을 모두 LOSE로 대체해도 괜찮은 이유는 into the unknown이기 때문이다.

table[A][B] 와 table[B][A] 둘 중 하나가 WIN이라면

A-B는 승패관계가 확실하다고 해석할 수 있기 때문이다.

 

 

 

 

 

플로이드 와샬 알고리즘을 참고한 블로그 - 나동빈 님!

24. 플로이드 와샬(Floyd Warshall) 알고리즘

 

해당 문제풀이를 참고한 블로그

프로그래머스 - 순위(Level 3)/Wanna Be 컴잘알