[C++] 백준 2578: 빙고

문제

[C++] 백준 2578: 빙고 SILVER 4
https://www.acmicpc.net/problem/2578

 

---

 

접근 방법

이 문제는 사회자가 숫자를 하나씩 부를 때마다, 현재 내 빙고판에서 몇 개의 빙고 줄이 완성되었는지를 확인해서
가장 처음으로 빙고 3줄 이상이 되는 순간의 호출 횟수를 출력하는 문제다.

 

기본 아이디어는 다음과 같이 잡았다.

1. 빙고판 입력
   • 5×5 빙고판을 vect[5][5]에 저장한다.
   • 이후 사회자가 부르는 숫자 25개를 call 벡터에 저장한다.
2. 숫자가 불릴 때마다 처리
   • find(call[i]) 함수로 현재 숫자 call[i]이 빙고판 어디에 있는지 찾아서 그 위치를 -1로 표시한다.
     (지워진 칸 = 체크된 칸)
   • 동시에, 그 칸의 좌표를 전역 변수 yy, xx에 저장해둔다.
3. 해당 위치 기준으로 빙고 줄이 몇 개 생겼는지 확인
   • check() 함수에서 새로 생긴 빙고 줄 개수를 계산해서 반환한다.
   • 매 호출마다 cnt += check(); 로 누적한 뒤,
   • 누적된 cnt가 처음으로 3 이상이 되는 순간의 호출 횟수(i + 1)를 출력하고 종료한다.

여기서 중요한 점은, 숫자 하나를 지웠을 때 빙고가 한 줄만 생기는 게 아니라 여러 줄이 한꺼번에 생길 수도 있다는 것.

예를 들어, 어떤 칸이 가로, 세로, 대각선에 모두 포함되는 교차점이었고 마지막 칸이었다면 → 한 번에 2줄, 심지어 3줄이 동시에 생길 수 있다.
그래서 check() 함수 안에서 이번에 생긴 빙고 줄이 총 몇 개인지 꼼꼼히 세서 리턴해 줘야 한다.

 

상세 아이디어

1) 숫자 위치 찾기 – find(call[i])

void find(int num)
{
    for (int y = 0; y < 5; y++)
    {
        for (int x = 0; x < 5; x++)
        {
            if (vect[y][x] == num)
            {
                vect[y][x] = -1;
                yy = y;
                xx = x;
                return;
            }
        }
    }
}

 

• 5×5 전체를 돌면서 num을 찾은 뒤,
  • 해당 칸을 -1로 표시 (지워진 칸)
  • 그 좌표를 yy, xx에 저장해둔다.
• 찾으면 바로 return해서 불필요한 탐색을 줄인다.

 

2) 새로 생긴 빙고 줄 개수 세기 – check()

check()에서는 이번에 방금 지운 칸(yy, xx) 을 기준으로 최대 4줄(가로, 세로, 두 대각선)을 검사한다.

여기서 핵심 포인트는 두 가지:

1. 한 번의 숫자 호출로 여러 줄이 동시에 완성될 수 있다.
   → 그래서 cnt를 1만 세는 게 아니라,
   가로/세로/대각선 각각에 대해 빙고가 되면 그때마다 cnt++ 해준다.
2. 이미 센 빙고 줄은 다시 세면 안 된다.
   → row[5], col[5], diag[2] 를 bool 전역 배열로 두고,
   한 번 빙고가 된 줄은 true로 바꿔 중복 카운트 방지를 한다.

int check()
{
    int cnt = 0;
    int rr = 0, cc = 0, diagL = 0, diagR = 0;
    if (row[xx] == false)
    {
        for (int i = 0; i < 5; i++)
        {
            if (vect[i][xx] == -1)
                rr++;
        }
        if (rr == 5)
        {
            cnt++;
            row[xx] = true;
        }
    }
    if (col[yy] == false)
    {
        for (int i = 0; i < 5; i++)
        {
            if (vect[yy][i] == -1)
                cc++;
        }
        if (cc == 5)
        {
            cnt++;
            col[yy] = true;
        }
    }
    if (diag[0] == false)
    {
        for (int i = 0; i < 5; i++)
        {
            if (vect[i][i] == -1)
                diagL++;
        }
        if (diagL == 5)
        {
            cnt++;
            diag[0] = true;
        }
    }
    if (diag[1] == false)
    {
        for (int i = 0; i < 5; i++)
        {
            if (vect[4 - i][i] == -1)
                diagR++;
        }
        if (diagR == 5)
        {
            cnt++;
            diag[1] = true;
        }
    }
    return cnt;
}

• 각 줄마다:
  • 이미 빙고로 센 줄(row[...], col[...], diag[...] == true)은 검사 생략
  • 아니라면 5칸이 전부 -1인지 확인
  • 다 -1이면 → 빙고 한 줄 추가 + 해당 줄을 true로 마킹

이렇게 해야 같은 줄을 두 번 이상 세지 않고, 한 번의 호출에서 여러 줄이 완성되는 경우도 정확하게 계산할 수 있다.

 

3) 메인 루프에서 빙고 3줄 조건 체크

    int cnt = 0;
    for (int i = 0; i < 25; i++)
    {
        find(call[i]);

        cnt += check();

        if (cnt >= 3)
        {
            cout << i + 1;
            return 0;
        }
    }

 

• 사회자가 숫자를 하나 부를 때마다:
  • 해당 숫자를 찾아 -1로 만들고
  • 이번 호출로 새로 생긴 빙고 줄 개수를 더해 나간다.
• cnt >= 3이 되는 순간이 “최초로 빙고가 3줄 이상 된 시점”이므로
  그때의 호출 횟수(i + 1)를 출력하고 종료한다.

 

---

 

코드

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> vect;
int yy, xx;
bool row[5];
bool col[5];
bool diag[2];

void find(int num)
{
    for (int y = 0; y < 5; y++)
    {
        for (int x = 0; x < 5; x++)
        {
            if (vect[y][x] == num)
            {
                vect[y][x] = -1;
                yy = y;
                xx = x;
                return;
            }
        }
    }
}
int check()
{
    int cnt = 0;
    int rr = 0, cc = 0, diagL = 0, diagR = 0;
    if (row[xx] == false)
    {
        for (int i = 0; i < 5; i++)
        {
            if (vect[i][xx] == -1)
                rr++;
        }
        if (rr == 5)
        {
            cnt++;
            row[xx] = true;
        }
    }
    if (col[yy] == false)
    {
        for (int i = 0; i < 5; i++)
        {
            if (vect[yy][i] == -1)
                cc++;
        }
        if (cc == 5)
        {
            cnt++;
            col[yy] = true;
        }
    }
    if (diag[0] == false)
    {
        for (int i = 0; i < 5; i++)
        {
            if (vect[i][i] == -1)
                diagL++;
        }
        if (diagL == 5)
        {
            cnt++;
            diag[0] = true;
        }
    }
    if (diag[1] == false)
    {
        for (int i = 0; i < 5; i++)
        {
            if (vect[4 - i][i] == -1)
                diagR++;
        }
        if (diagR == 5)
        {
            cnt++;
            diag[1] = true;
        }
    }
    return cnt;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	vect.resize(5, vector<int>(5, 0));
	for (int y = 0; y < 5; y++)
	{
		for (int x = 0; x < 5; x++)
		{
			cin >> vect[y][x];
		}
	}
    vector<int> call(25, 0);
    for (int i = 0; i < 25; i++)
        cin >> call[i];

    int cnt = 0;
    for (int i = 0; i < 25; i++)
    {
        find(call[i]);

        cnt += check();

        if (cnt >= 3)
        {
            cout << i + 1;
            return 0;
        }
    }
}