[ 프로그래머스 순위 (Lv3) ] (C++)

프로그래머스의 순위(Lv3) 문제이다.

[ 문제풀이 ]

정확하게 몇 등인지를 알 수 있는 선수가 몇 명인지 구해야 하는 문제이다.

선수1과 선수2가 있을 때, 선수1이 선수2를 이겼습니다 라는 문구가 주어지면 우리는 이를 통해서 다음과 같은 사실을

알 수 있다.

1. 선수1을 이긴 선수는, 선수2를 반드시 이길 수 있습니다.

2. 선수2에게 진 선수는, 선수1을 반드시 이길 수 없습니다.

그럼 위의 2가지 내용을 통해서 알아보자.

선수 A , B , C , D , E 5명이 있는 상황을 가정해보자. 그리고 다음과 같이 승패가 주어졌다고 가정해보자.

1. B가 A를 이겼습니다.

2. A가 C를 이겼습니다.

3. D가 B를 이겼습니다.

4. E가 C를 이겼습니다.

그럼 지금부터 위의 4가지 승패를 하나씩 파악해보자.

1. B가 A를 이겼습니다.

- 기존에 아무런 정보도 없었기에, 우리는 이정보를 통해서 알 수 있는 것은 A < B 라는 것 밖에 없다.

2. A가 C를 이겼습니다.

- A가 C를 이겼다는 것은, "A를 이긴사람은 당연히 C를 이길 수 있고, C에게 진 사람은 당연히 A에게 진다" 라는 것을 의미한다.

  그런데 우리가 기존에 알고 있는 사실은 ? A < B 라는 것이 있다.

  A가 C를 이겼는데, 이런 A를 B가 이겼기 때문에, B는 자연스럽게 C를 이길 수 있게 된다.

  즉, 우리는 이 정보를 통해서 , C < A , C < B 를 알 수 있다.

3. D가 B를 이겼습니다.

- D가 B를 이겼다면, B에게 진 선수들은 D에게도 반드시 진다는 것을 의미하고, D를 이긴 선수들은 B 또한 반드시 이길 수

  있다는 것을 의미한다.

  즉 ! 우리는 이 정보를 통해서 , B < D , A < D , C < D 를 알 수 있다.

  'A'와 'C'는 기존의 정보들을 통해서, 'B'에게 진 선수라는 것을 알고 있었고, 'B'에게 진 선수들은 절대로 'B'를 이긴

  'D'를 이길 수 없기 때문에 자연스럽게 위와 같은 정보를 알 수 있다.

4. E가 C를 이겼습니다.

- 우리는 이 내용을 통해서는 C < E 밖에 알 수가 없다. 왜냐하면, C < E면, E를 이긴 선수는 반드시 C를 이길 수 있다,

  혹은 C에게 진 선수는 반드시 E에게 진다 라는 것을 알 수 있는데, 우리가 가지고 있는 기존에 정보를 통해서는

  C에게 진 선수들, 혹은 E에게 이긴 선수들에 대한 정보가 없기 때문에 알 수가 없다.

그럼 위의 내용을 코드로 구현하는 과정을 알아보자.

1. 선수들 간의 관계를 저장해야 한다.

- 우리는 주어지는 정보들을 통해서, 누가 누구에게 승리했는지, 혹은 누가 누구에게 패배했는지를 계속해서

   체크해주면서 관계를 넓혀가고 있었다. 즉 ! 선수들 간에 "기존에 서로 비교한 적이 있는지, 없는지" 에 대해서

   판단해주어야 한다.

   이를 본인은 Compare[][] 이라는 2차원 배열을 만들어서 관리해 주었다.

   Compare[A][B] = true의 의미는 "선수 A와 선수 B는 이미 판단한 적이 있습니다" 를 의미한다.

2. 해당 선수를 이긴 선수와 진 선수를 저장해주어야 한다.

- 우리는 직접 비교해보지 않고도, 기존의 정보들을 통해서 승패를 알 수 있는 관계들이 있었따.

   예를 들어서 위에 2번 정보에서 "A가 C를 이겼다" 라는 정보를 통해서, "B가 C를 이길 수 있습니다" 라는 정보를

   얻어내었다.

   "B가 C를 이길 수 있습니다" 라는 정보를 알 수 있었던 것은 "B가 A를 이겼습니다." 라는 정보를 가지고 있었기

   때문이다. 즉 ! 어떤 선수가 어떤 선수를 상대로 이겼는지, 어떤 선수가 어떤 선수를 상대로 졌는지에 대한

   정보를 가지고 있어야 한다.

   그래서 본인은 vector배열을 사용해서 이를 저장해 주었다.

위의 2가지 관계를 이용하고 재귀를 통해서 문제를 해결하였다.

[ 소스코드 ]

#include <string>
#include <vector>
 
#define MAX 110
using namespace std;
 
vector<int> Win[MAX], Lose[MAX];
bool Compare[MAX][MAX];
 
void Make_Connect(int P1, int P2)
{
    for (int i = 0; i < Win[P1].size(); i++)
    {
        int P3 = Win[P1][i];
        if (Compare[P3][P2] == false)
        {
            Compare[P2][P3] = Compare[P3][P2] = true;
            Make_Connect(P3, P2);
            Win[P2].push_back(P3);
            Lose[P3].push_back(P2);
        }
    }
    for (int i = 0; i < Lose[P2].size(); i++)
    {
        int P3 = Lose[P2][i];
        if (Compare[P3][P1] == false)
        {
            Compare[P3][P1] = Compare[P1][P3] = true;
            Make_Connect(P1, P3);
            Win[P3].push_back(P1);
            Lose[P1].push_back(P3);
        }
    }
}
 
int solution(int n, vector<vector<int>> results) 
{
    int answer = 0;
    for (int i = 0; i < results.size(); i++)
    {
        int P1 = results[i][0];
        int P2 = results[i][1];
        if (Compare[P1][P2] == false)
        {
            Make_Connect(P1, P2);
            Compare[P1][P2] = true;
            Compare[P2][P1] = true;
            Win[P2].push_back(P1);
            Lose[P1].push_back(P2);
        }
    }
 
    for (int i = 1; i <= n; i++)
    {
        if (Win[i].size() + Lose[i].size() == n - 1) answer++;
        
    }
    return answer;
}