[ SWEA 5643 ] 키 순서 (C++)

SWExpertAcademy의 키순서(5643 / D4) 문제이다.

[ 문제풀이 ]

일부의 키 결과를 통해서 정확하게 자신의 키를 알 수 있는 학생이 몇 명이 구해야 하는 문제이다.

먼저, 자신의 키가 몇 번째인지 정확하게 알기 위한 방법에 대해서 부터 알아보자.

예를 들어서 3명의 학생이 있다고 가정해보자. [ 1번학생 , 2번학생 , 3번학생 ]

입력으로는 "1번학생은 2번학생보다 작습니다." , "2번학생은 3번학생보다 작습니다." 가 주어졌다고 생각해보자.

너무나 단순한 상황이라서 딱 봐도 3명 모두 자신이 몇 번째 인지 알 수 있을 거라는 결론이 나올 것이다.

그럼 왜 그렇게 되는지 알아보자. 분명히 2번학생은 모든 학생과 비교를 했지만, 1번학생과 3번학생은 비교하지 않았음에도

1번학생이 3번학생보다 더 작다는 것을 알 수 있다.

왜냐하면, 1번 학생은 2번학생보다 작은데, 2번학생은 3번학생보다 작기 때문에 당연하게 1번학생은 3번학생보다 작은 것이다.

굉장히 당연한 이야기지만 본인은 이 방법을 통해서 문제를 해결하였다.

문제에서 입력으로 일부 학생들의 키를 비교한 결과가 주어진다.

예를 들어서 A학생이 B학생보다 작다. 라는 식으로 입력이 주어지는데, 우리는 이 입력을 통해서 2가지 정보를 더 알 수 있다.

1. A학생보다 키가 작은 학생은, B학생보다 더 작다.

2. B학생보다 키가 큰 학생은, A학생보다 더 크다.

이를 구현하기 위해서 본인은, 2개의 Vector 배열을 사용해주었다.

하나는, 나보다 키가 작은 사람들을 저장해 놓는 Vector

또 하나는 나보다 키가 큰 사람들을 저장해 놓는 Vector

이 후, 재귀를 이용해서 위에서 말한 2가지 정보들을 저장해주었다. 이 과정에서 중복된 탐색이 발생할 수 있다.

따라서, 두 학생의 키 관계를 비교한 적이 있는지 없는지 판단해주기 위해서 Compare[][] 이라는 2차원 bool형 배열을 만들어서

관계를 비교한적에 대한 여부를 판단해 주었다.

재귀에 대한 부분을 코드로 보면 다음과 같다.

void Make_State(int A, int B)
{
    for (int i = 0; i < Small_Person[A].size(); i++)
    {
        int NA = Small_Person[A][i];
        if (Compare[NA][B] == false)
        {
            Compare[NA][B] = true;
            Compare[B][NA] = true;
            Big_Person[NA].push_back(B);
            Small_Person[B].push_back(NA);
            
            Make_State(NA, B);
        }
    }
    for (int i = 0; i < Big_Person[B].size(); i++)
    {
        int NB = Big_Person[B][i];
        if (Compare[NB][A] == false)
        {
            Compare[NB][A] = true;
            Compare[A][NB] = true;
            Big_Person[A].push_back(NB);
            Small_Person[NB].push_back(A);
 
            Make_State(A, NB);
        }
    }
}

위의 코드는 매개변수(A , B)가 주어지는데 이는 "A학생이 B학생보다 키가 더 작습니다" 라는 입력이 주어졌을 때

두 학생을 매개변수로 호출하는 코드이다.

위에서도 말했듯이 우리는 이 하나의 정보를 통해서 2가지 정보를 더 얻을 수 있다.

line3 ~ line15) 를 보게되면 "A학생보다 키가 작은 학생은 B학생보다 작습니다." 를 구현한 것이고

line16 ~ line 28) 을 보게되면 "B학생보다 키가 큰 학생은 A학생보다 큽니다." 를 구현한 것이다.

이런식으로 구현을 하게 되면, "현재 나보다 키가 작은사람은 Small_Person[] 이라는 Vector에, 나보다 키가 더 큰 사람은

Big_Person[] 이라는 Vector에 저장" 되어 있을 것이다.

그럼 총 학생수가 N명이기 때문에, Small_Person의 Size()와 Big_Person의 Size()를 비교해서 N - 1이 된다면,

즉, 나보다 키가 작은사람의 사람수 + 나보다 키가 큰 사람의 사람수를 더한 값이 전체 N명중, 나를 제외한 N - 1명이 된다면

자신의 키가 정확히 몇 번쨰인지 알 수 있게 된다.

[ 소스코드 ]

#include<iostream>
#include<vector>
#include<cstring>
 
#define endl "\n"
#define MAX 510
using namespace std;
 
int N, M, Answer;
bool Compare[MAX][MAX];
vector<int> Big_Person[MAX], Small_Person[MAX];
vector<pair<int, int>> Cmd;
 
void Initialize()
{
    memset(Compare, false, sizeof(Compare));
    for (int i = 0; i < MAX; i++)
    {
        Big_Person[i].clear();
        Small_Person[i].clear();
    }
    Cmd.clear();
    Answer = 0;
}
 
void Input()
{
    cin >> N >> M;
    for (int i = 0; i < M; i++)
    {
        int a, b; cin >> a >> b;
        Cmd.push_back(make_pair(a, b));
    }
}
 
void Make_State(int A, int B)
{
    for (int i = 0; i < Small_Person[A].size(); i++)
    {
        int NA = Small_Person[A][i];
        if (Compare[NA][B] == false)
        {
            Compare[NA][B] = true;
            Compare[B][NA] = true;
            Big_Person[NA].push_back(B);
            Small_Person[B].push_back(NA);
            
            Make_State(NA, B);
        }
    }
    for (int i = 0; i < Big_Person[B].size(); i++)
    {
        int NB = Big_Person[B][i];
        if (Compare[NB][A] == false)
        {
            Compare[NB][A] = true;
            Compare[A][NB] = true;
            Big_Person[A].push_back(NB);
            Small_Person[NB].push_back(A);
 
            Make_State(A, NB);
        }
    }
}
 
void Solution()
{
    for (int i = 0; i < M; i++)
    {
        int A = Cmd[i].first;
        int B = Cmd[i].second;
 
        if (Compare[A][B] == false)
        {
            Big_Person[A].push_back(B);
            Small_Person[B].push_back(A);
            Compare[A][B] = Compare[B][A] = true;
 
            Make_State(A, B);
        }
    }
 
    for (int i = 1; i <= N; i++)
    {
        int Cnt = Big_Person[i].size() + Small_Person[i].size();
        if (Cnt == N - 1) Answer++;
    }
}
 
void Solve()
{
    int Tc; cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
 
        cout << "#" << T << " " << Answer << endl;
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}