[ 백준 16986 ] 인싸들의 가위바위보 (C++)

백준의 인싸들의 가위바위보(16986) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 먼저, 이 문제에 어떻게 접근해야 하는지, 결론에 도달하기 위한 조건이 무엇인지, 입력이 의미하는것이 무엇인지 부터

   단계적으로 알아본 후에, 본격적인 구현에 들어가보도록 하자.

   일단 문제를 간단하게 요약하자면 "지우가 모든 판에서 손동작을 다르게 내어 우승할 수 있냐 !"를 묻는 것이다.

   그렇다면 지우가 이길 수 있는 경우는 어떤 경우들이 있을 지를 생각해보자.

   순서가, 지우 -> 경희 -> 민호 이기 때문에, 지우는 누구와 붙든, 무조건 이겨야지만 이겼다고 인정받는다.

   비기거나 질 경우에는 진 걸로 인정받게 된다. 왜냐하면 순서가 제일 앞이기 때문이다.

   또 하나를 더 생각해보자. 그렇다면 지우는 모든 판을 다 이겨야할까?? 아니다. 지거나 비기는 판도 있을 것이다.

   그래도 우승은 할 수 있다. 왜냐하면 이 문제에서 우승이라는 것이 'K승' 을 하는 것이지, '무패로 K승' 이 아니기 때문이다.

   즉, 우리는 계산을 할 때, 지우가 지더라도 우승할 수 있는 경우가 있는지 또한 체크를 해줘야 한다.

  

   이번에 이야기하고 싶은 것은 입력의 의미이다. 본인만 그런지 모르겠는데 입력을 이해하는데 시간이 꽤 걸렸다......

   (이 부분은 입력에 대한 이야기 이므로 입력에 대해서 잘 아시는 분들은 안 읽고 내려가셔도 좋습니다.)

   입력에 보면, NxN 형태의 2차원 맵 형태의 입력이 하나 주어진다. 이 것이 의미하는 것을 알아보자.

  

    위의 표는 예제입력1 을 가져온 것이다. 가장 왼쪽 상단을 (1, 1)이라고 표현한다면, (1, 1) ~ (3, 3)까지 각 칸에는

    0, 1, 2 3개의 숫자들 중 하나가 입력된다. 위의 맵을 A[3][3] 이라고 표시한다면,

    A[1][1] = 1인데, 1의 의미는 앞에 놈과 뒤에 놈이 비긴다는 의미이다.

    즉, 지우와 경희가 붙는데, 지우가 1을 내고 경희가 1을 내게 되면 둘이 비기게 된다는 것이다. 물론, 비길 경우 경희가

    승리하게 된다.

    A[1][2] = 0이다. 0의 의미는 앞에 놈이 뒤에놈한테 진다는 의미이다.

    즉, 지우와 경희가 붙는데, 지우가 1을 내고 경희가 2를 내게 되면 지우가 경희에게 진다는 의미이다.

    A[1][3] = 2이다. 2의 의미는 앞에 놈이 뒤에놈한테 이긴다는 의미이다.

    즉, 지우와 경희가 붙는데, 지우가 1을 내고 경희가 3을 내면 지우가 경희에게 이긴다는 의미이다.

    입력이 이러한 의미이다.

    그리고 밑에 보면 20개의 숫자들이 2줄로 쭉 나오게 되는데 이것은 20경기동안 경희와 민호가 내는 것들의 순서이다.

    입력에 대한 이야기는 여기까지만 하고, 문제에는 표현되어 있지 않은 지우가 우승하지 못하는 경우에 대해서 이야기를

    해보자. 먼저 지우는 "N판동안, K승"을 해야 한다. 우리는 여기서 지우가 절대 우승하지 못하는 한 가지 예외적인 경우를

    캐치해낼 수 있다. 바로 N < K 인 상황이다. 생각을 해보자. 지우가 낼 수 있는게 3개 뿐이다. 그런데 지우는 5승을 해야지만

    우승이 가능하다. 이게 가능할까? 당연히 불가능하다. 왜냐하면 지우는 모든 판 마다 다른 것을 내야하기 때문이다.

    또 한가지는 지우가 어떻게든 K승만 하면 우승일까?? 아니다. 그 전에 경희나 민호가 K승을 먼저 해버리면 그건 지우의

    우승이 아닌, 경희 or 민호의 우승이 되어버린다.

    즉, 지우는 N > K 인 상황에서, 경희 or 민호가 우승을 하기 전에 먼저 K승을 해서 우승을 해야한다.

    지금까지 했던 내용을 한번 정리를 해보자.

    1. 지우를 우승시켜야 한다.

    2. 그럼 지우는 무조건 이겨야 하나 ? 지거나 비길 수도 있다. K승만 하면 된다 ! 무패여야 하는 것은 아니다 !

    3. 경희 or 민호가 먼저 K승을 하게 될 경우, 지우는 우승을 하지 못한것이 된다.

   

2) 서론이 길었다. 본격적인 구현에 대해서 들어가보자.

   먼저 본인은 입력과 동시에 가위바위보의 상호관계(?)를 2차원 MAP에 저장해 주었다.

   그리고, 20판동안 경희와 민호가 내는 것을 RPS[][] 라는 2차원 배열을 하나 만들어서 저장해 주었는데

   이 때, 지우가 20판동안 내는 것은 -1로 모두 초기화를 시켜주었다.

   이 후, 순열을 구현해서 지우가 낼 것을 정해주었다. 갑자기 무슨 소리일까...

   생각을 해보자. 지우는 20판 중에 최대 N판만 참여할 수 있다. 왜 ? N개밖에 못내기 때문이다. 그 이상의 판을 하게 되면

   똑같은 것을 또 내야 하고, 결과적으로 우승을 하지 못하게 되는 것이다.

   즉, N판 동안 지우가 낼 것을 미리 정해주고, N판을 시행하는 것이다. 그럼 왜 순열일까 ??

   지우가 [ 1, 2, 3 ] 을 내는 것과, [ 2, 3, 1 ] 을 내는 것은 결과가 같을까?? 아니, 다를 것이다.

   분명히 1로는 못이기는 것을 2로는 이기거나 비길수도 있고, 2로는 못이기는 것을 3으로는 이기거나 비길 수도 있다.

   즉, 순서에 따라서 영향을 미치기 때문에 순열 구현을 통해서 지우가 N판 동안 낼 것을 미리 정해주었다.

   아직 순열을 구현하는 법을 잘 모른다면 아래의 글을 읽어보고 오자.

   [ 순열 구현하기 바로가기(Click) ]

  

   또 하나 주의해야 할 점은 입력으로 주어진 경희와 민호가 20판 동안 내는 것들과, 위에서 순열을 통해서 구현한

   지우가 내는 것들은 라운드 별 입력이 아니라는 것이다.

   예를 들어서 지우가 3 4 5 1 2 를, 경희가 1 2 3 4 5 를, 민호가 5 4 3 2 1 을 낸다고 생각해보자.

   그리고 첫 경기를 지우vs경희가 진행했다. 이 후에 지우vs민호가 경기를 했다고 하면, 민호는 4를 낼까 5를 낼까?

   5를 낸다는 것이다. 라운드 별로 생각한다면 민호의 1라운드 = 5, 2라운드 = 4 로 계산이 되지만 이 입력은

   라운드 별이 아닌 그냥 '순서' 일 뿐이다. 즉, 아직 민호는 첫 번째 순서인 5를 내지 않았기 때문에 자기 차례가 오면

   첫 번째 차례인 5를 내게 된다. 이 부분 주의하도록 하자.

   이 후, 본격적인 가위바위보는 재귀호출을 통해서 구현해보았다. 매개변수는 총 5개를 사용해 주었다.

    DFS(경기하는 사람1, 경기하는 사람2, 지우 순서, 경희 순서, 민호 순서)

    여기서 순서는 위에서 말한 '무엇을 낼지에 대한 순서' 를 의미한다.

    안에 구현한 구체적인 내용은 위에서 다 설명한 것들을 그대로 구현하였다.

    지우가 이기는 경우, 지는 경우에 대한 처리를 해 주었고, 모든 계산 후에 답을 출력하도록 해 주었다.

[ 소스코드 ]

#include<iostream>
 
#define endl "\n"
#define MAX 10
#define JW 1
#define GH 2
#define MH 3
using namespace std;
 
int N, K;
int MAP[MAX][MAX];
int RPS[4][21];
int Win_Num[4];
bool Select[MAX];
bool Flag;
bool Finish_Game;
 
void Input()
{
    cin >> N >> K;
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= N; j++)
        {
            cin >> MAP[i][j];
        }
    }
 
    for (int i = 2; i <= 3; i++)
    {
        for (int j = 1; j < 21; j++)
        {
            int a; cin >> a;
            RPS[1][j] = -1;
            RPS[i][j] = a;
        }
    }
}
 
bool Play_The_Game(int P1, int P2, int JW_Set, int GH_Set, int MH_Set)
{
    if (Win_Num[JW] >= K)
    {
        Finish_Game = true;
        return true;
    }
    if (Win_Num[GH] >= K || Win_Num[MH] >= K) return false;
    if (JW_Set > N) return false;
 
    int Next_Player;
 
    if ((P1 == 1 && P2 == 2) || (P1 == 2 && P2 == 1)) Next_Player = MH;
    else if ((P1 == 1 && P2 == 3) || (P1 == 3 && P2 == 1)) Next_Player = GH;
    else if ((P1 == 2 && P2 == 3) || (P1 == 3 && P2 == 2)) Next_Player = JW;
 
    if (Next_Player == JW)    // 지우가 NextPlayer다 == 지우가 현재 게임에 참가하지 않는다.
    {
        // 즉 이 경우는 경희 vs 민호. == 경희가 이기지 않는 이상 민호가 이긴다.
        if (MAP[RPS[GH][GH_Set]][RPS[MH][MH_Set]] == 2)
        {
            Win_Num[GH]++;
            Play_The_Game(GH, Next_Player, JW_Set, GH_Set + 1, MH_Set + 1);
            if (Finish_Game == true) return true;
            Win_Num[GH]--;
        }
        else
        {
            Win_Num[MH]++;
            Play_The_Game(MH, Next_Player, JW_Set, GH_Set + 1, MH_Set + 1);
            if (Finish_Game == true) return true;
            Win_Num[MH]--;
        }
    }
    else if(Next_Player == GH) // 경희가 NextPlayer다 == 경희가 현재 게임에 참가하지 않는다.
    {
        // 즉 이 경우는 지우 vs 민호의 경기. == 지우가 이기지 않는 이상 민호가 이긴다.
        if (MAP[RPS[JW][JW_Set]][RPS[MH][MH_Set]] == 2)
        {
            Win_Num[JW]++;
            Play_The_Game(JW, Next_Player, JW_Set + 1, GH_Set, MH_Set + 1);
            if (Finish_Game == true) return true;
            Win_Num[JW]--;
        }
        else
        {
            Win_Num[MH]++;
            Play_The_Game(MH, Next_Player, JW_Set + 1, GH_Set, MH_Set + 1);
            if (Finish_Game == true) return true;
            Win_Num[MH]--;
        }
    }
    else if (Next_Player == MH)
    {
        if (MAP[RPS[JW][JW_Set]][RPS[GH][GH_Set]] == 2)
        {
            Win_Num[JW]++;
            Play_The_Game(JW, Next_Player, JW_Set + 1, GH_Set + 1, MH_Set);
            if (Finish_Game == true) return true;
            Win_Num[JW]--;
        }
        else
        {
            Win_Num[GH]++;
            Play_The_Game(GH, Next_Player, JW_Set + 1, GH_Set + 1, MH_Set);
            if (Finish_Game == true) return true;
            Win_Num[GH]--;
        }
    }
}
 
void DFS(int Cnt)    // 지우가 낼 순서를 정해줌. 즉, 우리는 경기를 어떻게 N번할지는 모르지만, N번이 맞게 지우가 내는 순서를 정해놓을 수 있다.
{
    if (Flag == true) return;
    if (Cnt == N + 1)
    {
        Flag = Play_The_Game(1, 2, 1, 1, 1);
        return;
    }
 
    for (int i = 1; i <= N; i++)
    {
        if (Flag == true) return;
        if (Select[i] == true) continue;
        Select[i] = true;
        RPS[1][Cnt] = i;
        DFS(Cnt + 1);
        RPS[1][Cnt] = 0;
        Select[i] = false;
    }
}
 
void Solution()
{
    // 결국 지우는 N판 만에 쇼부를 쳐야함. 그 이상 되면 같은 걸 또내야 하기 때문에 절대로 이길 수가 없음.
    // 근데 경기순서가 1. 지우 2. 경희 3. 민호 임...
    // 그렇다면... 무조건 첫판은 지우 vs 경희가 되고 그 이 후에는 이 결과에 따라 달라지겟네?
    if (N < K)
    {
        cout << 0 << endl;
        return;
    }
    DFS(1);
    if (Flag == true) cout << 1 << endl;
    else cout << 0 << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}