백준 2578 빙고 c++ (구현)

문제 출처 : https://www.acmicpc.net/problem/2578

2578번: 빙고

문제

빙고 게임은 다음과 같은 방식으로 이루어진다.

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

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

 

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

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

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

입력

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

출력

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

알고리즘 분류

• 구현

풀이

문제 풀이의 감을 익히기 위한 구현 문제이다.

주어진 입력은 크지 않으므로 완전 탐색으로 풀면 된다.

우선 2차원 배열로 빙고 판을 만들고, 입력되는 수들의 좌표를 기억해놨다가,

사회자가 부르는 숫자를 가지고 있다면 빙고판의 해당 숫자가 있는 좌표의 숫자를 0으로 바꾼다.

이후, 가로, 세로를 모두 검사하고 대각선까지 검사하여 3줄 이상 빙고가 나온다면 종료!

사회자가 10개 이하로 수를 불렀을 때는 3빙고가 나올 수 없으니 11개 이상 불렀을 때부터 검사한다.

 

코드

#include <iostream>

using namespace std;
int arr[5][5];
pair<int, int> num[26];

bool check() {
	int bingo = 0;
	int crossR = 0;
	int crossL = 0;
	for (int i = 0; i < 5; i++) {
		int col = 0;
		int row = 0;
		for (int j = 0; j < 5; j++) {
			if (arr[i][j] == 0) {
				row++;
			}
			if (arr[j][i] == 0) {
				col++;
			}
		}
		if (col == 5) {
			bingo++;
		}
		if (row == 5) {
			bingo++;
		}
		if (arr[i][i] == 0) {
			crossR++;
		}
		if (arr[i][4-i] == 0) {
			crossL++;
		}
	}
	if (crossR == 5) {
		bingo++;
	}
	if (crossL == 5) {
		bingo++;
	}
	if (bingo >= 3) {
		return true;
	}
	return false;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	for (int i = 0; i < 5; i++) {
		for (int j = 0; j < 5; j++) {
			cin >> arr[i][j];
			num[arr[i][j]] = { i,j };
		}
	}
	int ans = 0;
	for (int i = 0; i < 5; i++) {
		for (int j = 0; j < 5; j++) {
			ans++;
			int number;
			cin >> number;
			arr[num[number].first][num[number].second] = 0;
			if (i > 1) {
				if (check()) {
					cout << ans;
					return 0;
				}
			}
		}
	}




	return 0;
}