백준 17349번 1루수가 누구야 C++ (골드4)

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

 

단순해 보이지만 생각할게 은근 많은 문제였다.

 

우선 선수를 한명씩 지정하여 거짓말을 하고 있다고 가정하고 지정한 선수의 말을 바꿔서 모두 옳은말을 하고 있다고 가정한다.

 

여기서 두 사람의 말이 다르다면 모순인 상황이고, 바로 스킵해준다.

 

특정 선수를 1루수라고 주장하는 사람이 1명이라면, 그 경우에서는 주장한 사람이 지정한 선수가 1루수가 맞다.

특정 선수를 1루수라고 주장하는 사람이 2명 이상이라면 틀린 경우이다.

특정 선수를 1루수라고 주장하는 사람이 0명이라면 8명이 1루수라고 주장하지 않았을때만 나머지 1명이 1루수가 될 수 있다.

 

즉, 특정 선수를 1루수라고 주장하는 사람이 1명이거나 1루수가 아니라고 주장하는 경우가 8가지 경우일 때 한명이 1루수가 될 수 있다.

 

그런데 위의 경우가 2번이상 나온다면 1루수가 누구인지 확신할 수 없어진다.

그렇기 때문에 1루수가 누구인지 확신할 수 있는 경우는 단 한번만 나와야 한다.

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <limits.h>

using namespace std;
using int64 = long long;

vector<pair<int, int>> v(9);

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    for (int i = 0; i < 9; i++)
    {
        cin >> v[i].first >> v[i].second;
    }
    
    int ans = -1;
    int possibleAnsCnt = 0;
    for (int i = 0; i < 9; i++)
    {
        int lierCheck = i;
        map<int, int> m;
        bool _continue = false;
        bool _findAns = false;
        for (int j = 0; j < 9; j++)
        {
            int player = v[j].second;
            int opinion = v[j].first;
            // 한명씩 거짓말을 하고있다고 가정하고 거짓말을 반대로 바꾸기
            if (j == lierCheck) opinion = (opinion + 1) % 2;
            auto it = m.find(player);
            // 이미 해당 선수에 대한 주장이 있다면
            if (it != m.end()) {
                // 주장이 일치한다면
                if (m[player] == opinion)
                {
                    
                }
                else { // 주장이 일치하지 않는다면 모순
                    _continue = true;
                    break;
                }
            }
            else {
                m.insert(make_pair(player, opinion));
            }
        }
        if (_continue) continue;

        // 1루수가 1명이라면 정답
        // 1루수가 2명이상이면 바꾼 사람이 거짓말을 하지 않은 사람이었음
        // 1루수가 0명이라면 -> 8명이 1루수가 아니라면 나머지 1사람이 1루수
        int firstSacker = -1;
        int notFirstSacketCount = 0;
        for (auto a : m)
        {
            if (a.second == 1)
            {
                // 처음 찾은 1루수면 일단 정답으로 지정
                if (firstSacker == -1)
                {
                    firstSacker = a.first;
                    _findAns = true;
                }
                else { //찾다보니 1루수가 2명이면 모순
                    _findAns = false;
                }
            }
            else {
                notFirstSacketCount++;
            }
        }
        if (notFirstSacketCount == 8) _findAns = true;
        if (_findAns)
        {
            if (firstSacker != -1)
            {
                ans = firstSacker;
            }
            else {
                set<int> candidates = { 1,2,3,4,5,6,7,8,9 };
                for (auto a : m)
                {
                    candidates.erase(a.first);
                }
                ans = *candidates.begin();
            }
            possibleAnsCnt++;
        }
        else {
            if (firstSacker == -1)
            {
                possibleAnsCnt += 9 - notFirstSacketCount;
            }
        }
    }
    if (possibleAnsCnt == 1)
    {
        cout << ans;
    }
    else {
        cout << -1;
    }
}