[ boj : 16986 ] 인싸들의 가위바위보

https://www.acmicpc.net/problem/16986

16986번: 인싸들의 가위바위보

문제 : 문제 생략 그냥 보고 오세요;;(ㅈㅅㅈㅅ;; 너무길어 ㅠㅠ)

해설 : 후,,,문제 잘 읽어야 되요 ㅠㅠ정말로 정말로

먼저 주의해야 될 점을 말씀드리면

1. 세명 중에 단 한명이라도 우승한다면 게임은 끝납니다. 전 처음에 무조건 지수만 우승하는 경우만 생각해주고 나머지는 이기든 지든 전혀 신경도 쓰지 않았지만 이렇게 한다면 안됩니다. 다른 사람이 우승을 해버리면 return시켜주는 방향으로!
2. 20경기에 대해 어떤 가위바위보를 낼지 입력이 주어지는데 이는 절대로 라운드가 아닙니다. 그냥 순서대로 내는 것 입니다. 그러니 만약 현재 경기에 참여를 하지 않은 선수는 입력값을 띄어넘지 않고 그대로 멈추게 되는 것 입니다.
3. 지수가 지더라도 반드시 어떤 가위바위보는 내는 것입니다. 그러니 이에 대한 체크가 반드시 필요 합니다.
4. 순서를 반드시 확인해야 합니다. 전의 경기와 상관없이 주어진 지수 > 경희 > 민호 의 순서대로 경기가 진행됩니다.

이 문제;;;; 역시 빠킹독님 문제입니다 ㅠㅠ 아마 삼성 시험 대비문제로 만드셨던 것 같으신데 하나씩 살펴 보시죠.

먼저 나올 수 있는 케이스는 총 3가지 입니다.

1. 지수 vs 경희
2. 지수 vs 민호
3. 경희 vs 민호

우리는 지수를 0, 경희를 1, 민호를 2 라고 합시다.
그리고 이 세가지 케이스를 나누어서 각자 처리를 해주는 것입니다.

1번과 2번은 visit배열을 선언해서 지수가 어떤 가위바위보를 냈는데 체크를 해주고 3번은 그냥 둘만 비교하여 이기는 쪽만 재귀함수에 넣어주면 됩니다.

이때 경희와 민호가 어떤 가위바위보를 낼지는 변수 l 과 r 로 선언해주어 구분해줍시다.

3번의 경우에는 adj 배열의 상태값에 따라 그냥 1,0 이면 민호가 2이면 경희가 이기게끔 해주면 되지만 1번과 2번은 지수가 어떤 가위바위보를 낼지 모릅니다.
따라서 반대로 생각해서 경희나 민호가 낼 가위바위보의 값에 해당하는 열에 adj값이 0이라면 무조건 지수가 이기게 되는 것이니 이렇게 처리를 해줍시다.

그럼 다 끝났습니다. score배열 3칸짜리를 선언해주고 각 선수들의 점수들을 계산해주어 지수가 k 번 이상 이겼으면 성공, 아니라면 실패로 처리해주면 됩니다.

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

int n, k;
int adj[9][9];
int arr[2][20];
int score[3];
int visit[9];
int ans;

void input();
bool check();
void f(int x, int y, int l, int r);

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    input();
    f(0, 1, 0, 0);
    cout << ans;
    return 0;
}
void f(int x, int y,int l,int r)
{
    if (score[0] >= k) {
        ans = 1;
        return;
    }
    if (score[1] >= k || score[2] >= k)return;

    if (check())return;

    //지우 vs 경희
    if (x == 0 && y == 1) {
        for (int i = 0; i < n; i++) {
            if (visit[i] == 1)continue;
            int p = arr[0][l];

            visit[i] = 1;
            if (adj[p][i] == 0) {//지우 승
                score[x]++;
                f(x, 2, l + 1, r);
                score[x]--;
            }
            else {//경희 승
                score[y]++;
                f(y, 2, l + 1, r);
                score[y]--;
            }
            visit[i] = 0;
        }
    }
    //지우 vs 민호
    else if (x == 0 && y == 2) {
        for (int i = 0; i < n; i++) {
            if (visit[i] == 1)continue;
            int p = arr[1][r];

            visit[i] = 1;
            if (adj[p][i] == 0) {//지우 승
                score[x]++;
                f(x, 1, l, r + 1);
                score[x]--;
            }
            else {//민호 승
                score[y]++;
                f(1, y, l, r + 1);
                score[y]--;
            }
            visit[i] = 0;
        }
    }
    //경희 vs 민호
    else {

        int p = arr[0][l];
        int q = arr[1][r];

        if (adj[p][q] <= 1) {//민호 승
            score[y]++;
            f(0, 2, l + 1, r + 1);
            score[y]--;
        }
        else {//경희 승
            score[x]++;
            f(0, 1, l + 1, r + 1);
            score[x]--;
        }        
    }
}
bool check()
{
    int cnt = 0;
    for (int i = 0; i < n; i++)
        if (visit[i] == 1)
            cnt++;
    if (cnt >= n)return true;
    return false;
}
void input()
{
    cin >> n >> k;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) {
            cin >> adj[i][j];
        }
    for (int i = 0; i < 20; i++) {
        cin >> arr[0][i];
        arr[0][i]--;
    }
    for (int i = 0; i < 20; i++) {
        cin >> arr[1][i];
        arr[1][i]--;
    }
}