[C/C++] 백준 #2578 빙고(구현)

이번 문제는 알고리즘적으로 특별한 것이 없고, 스도쿠, 노노그램 등에서 사용할만한 기법을 소개하도록 하겠습니다.

 

bingo

 

문제의 링크는 다음과 같습니다.

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

2578번: 빙고

 

이러한 문제를 풀 때에는 플래그를 사용하면 편합니다.  플래그를 이용해서 현재의 상황을 요약을 하는 기술입니다.

빙고의 각 줄과 각 열, 두개의 대각선을 각각 하나의 플래그로 놓고서, 몇개가 맞는지 계속 기록하는 방식입니다.

 

(r, c) 위치가 맞았다고 한다면, rowCount[r] 을 하나 증가 시키고, colCount[c]를 하나 증가시킵니다.  또한 r과 c가 같다고 한다면, dia1 을 증가시키고, r과 c를 합한 값이 4가 된다면, dia2를 증가시키는 것이죠.  이렇게 하면, 매번 보드를 탐색하지 않아도 손쉽게 맞은 열의 개수와 줄의 개수, 그리고 대각선의 개수를 구할 수 있습니다.

 

이러한 기법을 아는 것은 프로그램을 작성할 때 매우 유용하게 사용됩니다.

 

다음은 제가 작성한 소스입니다.

//------------------------------------------------
//    baekjoon #2578
//        - by Aubrey Choi
//        - created at 2019-11-13
//------------------------------------------------
#include <stdio.h>

int main()
{
    int b[25], s, h[5]={0,}, v[5]={0,}, d[2]={0,}, i, cnt=0;
    for(i=0;i<25;i++) { scanf("%d",&s); b[s-1]=i; }
    for(i=1;;i++)
    {
        scanf("%d",&s); s=b[s-1];
        if(++h[s/5]==5) cnt++;
        if(++v[s%5]==5) cnt++;
        if((s/5)==(s%5)&&(++d[0])==5) cnt++;
        if((s/5+s%5)==4&&(++d[1])==5) cnt++;
        if(cnt>=3) break;
    }
    printf("%d\n",i);
}