[BOJ/C++] 16624 - Bingo Ties

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

 

---

 

팀원들과 ICPC 골랜디 연습 중에 찾은 문제였습니다. 

 

 

n개의 5*5 빙고판이 있고, 무승부 즉, 동시에 빙고가 되는 판의 쌍이 존재하는 지 찾는 문제입니다. 

여기서, 빙고는 대각선, 세로를 제외한 가로줄만 인정합니다.

 

 

가장 먼저 떠올린 풀이는, 빙고판의 숫자가 최대 3000이기 때문에, 가능한 모든 빙고 조합에 대해서 완전탐색하고자 하였습니다.

그렇게 되면, 모든 조합은 3000C5 = 약 2000조...이기때문에 시간 안에 돌기에는 무리가 있습니다.

여기서 n이 100이고, 빙고판은 5*5이므로 모든 빙고판에 중복없이 작성한다면 총 100*5*5 = 2500 가지의 숫자가 적히므로, 줄여도 2500C5 = 약 800조로 마찬가지로 시간을 맞추기 어렵습니다.

 

 

때문에, 우리는 조금 더 똑똑하게 풀 방법을 찾아야 합니다. 

생각해보면, 동시에 빙고가 되려면 두 빙고판엔 중복된 숫자가 반드시 존재해야합니다.

그렇지않으면 무조건 한쪽만 빙고가 되겠죠?

 

근데 반대로, 두 빙고판에 중복된 숫자가 있다면 반드시 무승부가 날까요?

답은 '아니오'입니다.

두개의 빙고판에서, 숫자 x가 중복된 숫자라고 생각해봅시다.

x가 무승부가 되려면, x가 위치한 행의 나머지 4개의 숫자가 우선적으로 나온후에, x가 나온다면 무승부가 될 것입니다.

두개의 빙고판에서 각각 x의 행의 4개 숫자가 나와야 하므로,

두 빙고판이 무승부가 되려면 x에 앞서서 나와야 하는 숫자는 최대 8개 입니다. 

하지만, x에 앞서서 나오는 숫자들로 빙고를 만들수 있는 빙고판이 있다면? 무승부가 나지 않을 것 입니다. 

 

두 빙고판에 중복된 숫자가 있어도 무승부가 나지 않는다는 반례 테스트케이스입니다. 

3
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15 
16 17 18 19 20
21 22 23 24 25

1 26 27 28 29
30 31 32 33 34
35 36 37 38 39 
40 41 42 43 44
45 46 47 48 49

2 3 4 26 27
50 51 52 53 54
55 56 57 58 59
60 61 62 63 64
65 66 67 68 69

 

해당 테스트케이스의 답은 1 3입니다.

1번, 2번 빙고판의 1행에 1이 중복되어있지만, [2,3,4,5],[26,27,82,29]를 채우게 된다면 3번 빙고판이 빙고가 됩니다. 

 

따라서 우리가 작성해야하는 코드는,

1. 두 쌍의 빙고판에 대해서 중복된 숫자 x를 찾고,

2. x를 포함하는 행의 다른 숫자들로 빙고를 만들 수 있는지 검사해야합니다. 

 

아래는 답안코드입니다.

#include<bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define rep(i,x,y) for(ll i=x;i<y;i++)
#define all(x) begin(x),end(x)
#define rall(x) rbegin(x),rend(x)
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef tuple<int,int,int> tiii;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
/*----------------------*/

int n; 
vector<vector<int>> loc;
vector<vector<int>> board;

void findBingo(int a, int b, int dupVal, int a_row, int b_row){

    vector<bool> chk(3001,0);
    rep(i,0,5){
        chk[board[a][a_row*5+i]] = 1;
        chk[board[b][b_row*5+i]] = 1;
    }
    chk[dupVal] = 0;

    rep(i,0,n){
        if(i==a||i==b) continue;
        rep(r,0,5){
            int cnt = 0;
            rep(c,0,5) cnt += chk[board[i][r*5+c]];
            if(cnt==5) return;
        }
    }
    cout<<a+1<<' '<<b+1<<'\n';
    exit(0);
}
int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>n;
    loc.resize(n);
    board.resize(n);
    rep(i,0,n){
        loc[i] = vector<int>(3001,-1);
        rep(j,0,25){
            int x; cin>>x;
            board[i].push_back(x);
            loc[i][x] = j/5;
        }
    }

    rep(i,0,n) rep(j,i+1,n){
        rep(idx,0,25){
            if(loc[i][board[j][idx]]==-1) continue;
            // i와 j에 board[j][idx]값이 중복
            // 중복값은 i의 loc[i][board[j][idx]]행에, j의 idx/5행에 위치
            findBingo(i, j, board[j][idx], loc[i][board[j][idx]], idx/5);

        }
    }
    cout<<"no ties\n";
}

 

 

가능한 서로 다른 빙고판 쌍 i, j를 선택하고, 

빙고판을 순회하며 i와 j 사이에 중복된 수 x를 체크하고, 

중복값이 있다면, i와 j를 제외한 다른 보드판에서 x가 속한 행의 원소들로 빙고를 만들 수 있는지 확인합니다.

 

시간복잡도는

가능한 i,j에 대해 확인하므로 O(n*n).

i, j 빙고판에 중복을 찾기 위해 O(25).

findBingo()에서 i,j를 제외한 순회하므로 O(n-2). 상수 무시하면 O(n).

빙고가 만들어지는지 확인하기위해 O(25)

따라서 O(n*n*n*25*25).

n이 최대 100이므로 약 625,000,000 입니다. 

6억이라 2초안에 돌아갈 수 있을지 의심이 되긴 하지만, 실제로는 생각하시는 것보다 더 빠르게 동작합니다. 

저의 경우 12ms만큼 걸렸네요.

 

중복값이 존재하면 무조건 무승부가 일어난다!의 반례를 찾지 못해서 여러번 시도했던 문제였습니다. 

14번 틀렸다가.. 반례찾고 코드 고쳐서 금방 맞췄습니다. 기분이 좋네요 ㅎ