백준 16624번 Bingo Ties [C++]

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

 

 

 

#문제 간단 정리

 

이 문제는 동시에 빙고가 나오는지 확인을 하면 되는데

빙고는 행 빙고만 취급한다.

 

#문제 해결 방법

 

만약 두 빙고카드에 같은 행에

같은 숫자가 존재한다면 

비길 수 있는 가능성으로 만드는 가능성이 존재한다.

 

하지만 만약

1 2 3 4 5

1 6 7 8 9

2 3 4 6 7

 

1 2 3 4 5

에서 1을 찾고

1 6 7 8 9 

에서 1을 찾아서

 

비긴다고 생각을해도

 

나머지 2 3 4 5, 6 7 8 9

을 빙고하다보면

2 3 4 6 7 행이 빙고가 되서 비기지 않는다

 

즉 다른카드에서 겹치는 쌍을 찾고

1 2 3 4 5 에서 1을 골랏다면 2 3 4 5 를 추출

1 6 7 8 9 에서 1을 골랏다면 6 7 8 9 를 추출해서

2 3 4 5 6 7 8 9 로 이루어진 빙고가 없는지 조사해야된다.

 

 

#전체 코드

#include <iostream>
#include <vector>
#include <set>

using namespace std;

vector<vector<vector<int>>> numbers;
int n;

//각 행이 나머지 숫자들로 빙고가 되는지 학인하기 , 빙고가 안된다면 false 된다면 true
bool remainMatch(vector<int>& remainOne, vector<int>& remainTwo, int dupi1, int dupj1, int dupi2, int dupj2) {

    for (int i = 0; i < n; i++) {

        for (int j = 0; j < 5; j++) {
            //같은세트의 같은 행은 조사하지 않음
            if (i != dupi1 || j != dupj1) {
 
                if (i != dupi2 || j != dupj2) {


                    vector<bool> check(5, false);

                    for (int k = 0; k < 5; k++) {

                        for (auto a : remainOne) {
                            if (numbers[i][j][k] == a) {
                                check[k] = true;

                            }
                        }
                        for (auto a : remainTwo) {
                            if (numbers[i][j][k] == a) {
                                check[k] = true;
                            }
                        }

                    }

                    bool allCheck = true;
                    for (auto a : check) {
                        if (!a) {
                            allCheck = false;
                        }
                    }
                    //전부 true 면 false 반환

                    if (allCheck) {

                        return true;
                    }

                }
            }

        }


    }

    return false;
}

int main() {

    cin >> n;

    for (int i = 0; i < n; i++) {
        vector<vector<int>> temp(5, vector<int>(5));
        for (int u = 0; u < 5; u++) {
            for (int j = 0; j < 5; j++) {
                cin >> temp[u][j];
            }
        }

        numbers.push_back(temp);
    }

    //일치되는 숫자를 찾고 , 일치되는 숫자 쌍의 행에서 나머지를 추출해서 그 나머지들로 이뤄지는 빙고가 있는지 확인
    for (int i = 0; i < n; i++) {
        for (int k = 0; k < 5; k++) {
            for (int t = 0; t < 5; t++) {
                int target = numbers[i][k][t];

                vector<int> remainOne;

                for (int b = 0; b < 5; b++) {
                    if (b == t) continue;
                    //추출한 첫번쨰 숫자의 나머지 행의 원소들 저장
                    remainOne.push_back(numbers[i][k][b]);
                }

                //다음 빙고셋트들 확인
                for (int j = i + 1; j < n; j++) {

                    for (int p = 0; p < 5; p++) {
                        for (int l = 0; l < 5; l++) {
                            if (target == numbers[j][p][l]) { //같으면 나머지 챙겨서 확인

                                vector<int> remainTwo;

                                for (int b = 0; b < 5; b++) {
                                    if (b == l) continue;
                                    //일치한 두번째 숫자의 나머지 행의 원소들 저장
                                    remainTwo.push_back(numbers[j][p][b]);
                                }


                                if (!remainMatch(remainOne, remainTwo, i, k, j, p)) {
                                    cout << i + 1 << ' ' << j + 1 << '\n';
                                    return 0;
                                }


                            }
                        }
                    }

                }

            }
        }
    }

    cout << "no ties" << '\n';
    return 0;
}