실력키우기 빙고(C++)

1031 : 빙고

제한시간: 1ms    메모리제한: 32MB
해결횟수: 970회    시도횟수: 2314회   

빙고 게임은 다음과 같은 방식으로 이루어진다.먼저 아래와 같이 25개의 칸으로 이루어진 빙고판에 1부터 25까지 자연수를 한 칸에 하나씩 쓴다.

 

 

다음은 사회자가 부르는 수를 차례로 지워나간다. 예를 들어 5 10 7이 불렸다면 이 세 수를 지운 뒤 빙고판의 모습은 다음과 같다.

 

 

차례로 수를 지워가다가 같은 가로줄 세로줄 또는 대각선 위에 있는 5개의 모든 수가 지워지는 경우 그 줄에 선을 긋는다.

 

 

이러한 선이 세 개 이상 그어지는 순간 "빙고"라고 외치는데 가장 먼저 외치는 사람이 게임의 승자가 된다.

 

 

철수는 친구들과 빙고 게임을 하고 있다. 철수가 빙고판에 쓴 수들과 사회자가 부르는 수의 순서가 주어질 때 사회자가 몇 번째 수를 부른 후 철수가 "빙고"를 외치게 되는지를 출력하는 프로그램을 작성하시오.

 

첫째 줄부터 다섯째 줄까지 빙고판에 쓰여진 수가 가장 위 가로줄부터 차례대로 한 줄에 다섯 개씩 빈 칸을 사이에 두고 주어진다.
여섯째 줄부터 열째 줄까지 사회자가 부르는 수가 차례대로 한 줄에 다섯 개씩 빈 칸을 사이에 두고 주어진다.
빙고판에 쓰여진 수와 사회자가 부르는 수는 각각 1부터 25까지의 수가 한 번씩 사용된다.

첫째 줄에 사회자가 몇 번째 수를 부른 후 철수가 "빙고"를 외치게 되는지 출력한다.

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

[Copy] 15

?

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 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105

/**************************************************************     Problem: 1031     User: a132034     Language: C++     Result: Success     Time:2 ms     Memory:1740 kb ****************************************************************/     #include    <iostream> using namespace std; #define N 5 #define CHECK 1 #define UNCHECK 0   bool bingo(int map[][5]);   int main() {     int chulsu[N][N];     int map[N][N];     int num;       for (int i = 0; i < N; ++i)     {         for (int j = 0; j < N; ++j)         {             cin >> chulsu[i][j];             map[i][j] = UNCHECK;         }     }       for (int k = 0; k < N*N; ++k)     {         cin >> num;           for (int i = 0; i < N; ++i)         {             for (int j = 0; j < N; ++j)             {                 if (num == chulsu[i][j])                     map[i][j] = CHECK;             }         }           if (bingo(map))         {             cout << k+1 << endl;             return 0;         }     }     return 0; }   bool bingo(int map[][5]) {     int count = 0;     bool check;     //가로 체크     for (int i = 0; i < N; ++i)     {         check = true;           for (int j = 0; j < N; ++j)             if (map[i][j] == UNCHECK)                 check = false;           if (check)             count++;           check = true;         for (int j = 0; j < N; ++j)             if (map[j][i] == UNCHECK)                 check = false;           if (check)             count++;     }       //대각선 체크       check = true;     for (int i = 0; i < 5; ++i)     {         if (map[i][i] == UNCHECK)             check = false;     }     if (check)         count++;       check = true;     for (int i = 0; i < 5; ++i)     {         if (map[N - i - 1][i] == UNCHECK)             check = false;     }     if (check)         count++;       if (count >= 3)         return true;     else         return false; }

큰 판이 아니고 5X5로 정해져 있는 빙고였기 때문에 특별한 알고리즘이 필요하지는 않았다.

한 숫자가 불릴 때 마다 처음부터 빙고를 계산하였다. 

계산은 가로줄, 세로줄, 대각선을 체크하면 된다.

만약 판이 엄청나게 커지거나, 다른 복잡한 제약사항이 생기면 이렇게 숫자를 하나 부를 때 마다 전체를 탐색하는 방식을 쓰면 시간이 엄청나게 오래걸릴것 같다.