[백준 C++] 2140 지뢰찾기

문제

지뢰찾기는 N×N에서 이뤄지는 게임이다. 보드의 곳곳에는 몇 개의 지뢰가 숨겨져 있고, 지뢰가 없는 칸에는 그 칸과 인접(상하좌우 및 대각선)해 있는 8개의 칸들에 몇 개의 지뢰가 숨겨져 있는지에 대한 정보가 주어진다. 게이머는 게임을 진행하면서 보드의 칸을 하나씩 열게 된다. 만약 그 칸에 지뢰가 있다면 게임이 끝나고, 없는 경우에는 그 칸에 적혀있는 숫자, 즉 그 칸과 인접해 있는 8개의 칸들 중 몇 개의 칸에 지뢰가 있는지를 알 수 있게 된다.

이 문제는 보드의 테두리가 모두 열려있고, 그 외는 모두 닫혀있는 상태에서 시작한다. 예를 들어 다음과 같은 경우를 보자.

#는 닫혀있는 칸을 나타낸다. 이러한 보드가 주어졌을 때, 닫혀있는 칸들 중 최대 몇 개의 칸에 지뢰가 묻혀있는지 알아내는 프로그램을 작성하시오. 위의 예와 같은 경우에는 다음과 같이 6개의 지뢰가 묻혀있을 수 있다.

입력

첫째 줄에 N(1≤N≤100)이 주어진다. 다음 N개의 줄에는 N개의 문자가 공백 없이 주어지는데, 이는 게임 보드를 의미한다.

출력

첫째 줄에 묻혀있을 수 있는 지뢰의 최대 개수를 출력한다.

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

풀이

포인트는 이미 모서리4군데에 인접한 4군데는 지뢰가있는지 없는지 (1,1) , (1,n-2) , (n-2, n-2) , (n-2, 1) 알수 있음.

이렇게 4방향으로 탐색을하며,

파란색물음표위치인 2군데의 지뢰수를 세고, 보라색위치의 지뢰갯수가 이보다 크면 빨간색위치에 지뢰를 놓으면된다.
이런식으로 n-2 까지 반복한다. (그리고 4방향으로)

#define _CRT_SECURE_NO_WARNINGS 
#include <bits/stdc++.h>
int n, **map;

void vertex_check() { //4방향꼭짓점 check
	if (map[0][0] == 1) map[1][1] = -1;
	if (map[n - 1][0] == 1) map[n - 2][1] = -1;
	if (map[0][n - 1] == 1) map[1][n - 2] = -1;
	if (map[n - 1][n - 1] == 1) map[n - 2][n - 2] = -1;
}

void playGame() {
	for (int i = 1; i <= n - 3; i++) { //상
		int mineCnt = 0;
		if (map[1][i - 1] == -1) mineCnt++;
		if (map[1][i] == -1) mineCnt++;
		if (mineCnt < map[0][i]) map[1][i + 1] = -1; //우하단위치에 지뢰check
	}

	for (int i = 1; i <= n - 3; i++) { //우
		int mineCnt = 0;
		if (map[i - 1][n - 2] == -1) mineCnt++;
		if (map[i][n - 2] == -1) mineCnt++;
		if (mineCnt < map[i][n - 1]) map[i + 1][n - 2] = -1;
	}

	for (int i = 1; i <= n - 3; i++) { //하
		int mineCnt = 0;
		if (map[n - 2][i - 1] == -1) mineCnt++;
		if (map[n - 2][i] == -1) mineCnt++;
		if (mineCnt < map[n - 1][i]) map[n - 2][i + 1] = -1; 
	}

	for (int i = 1; i <= n - 3; i++) { //좌
		int mineCnt = 0;
		if (map[i - 1][1] == -1) mineCnt++;
		if (map[i][1] == -1) mineCnt++;
		if (mineCnt < map[i][0]) map[i + 1][1] = -1;
	}

}

int sum() {
	int res = 0;
	if(n >= 5)
		res = (n - 4) * (n - 4);
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			if (map[i][j] == -1)
				res++;
	//for (int i = 0; i < n; i++) {
	//	for (int j = 0; j < n; j++)
	//		printf("%2d", map[i][j]);
	//	printf("\n");
	//}
		
	return res;
}

int main(char c) {
	scanf("%d", &n);
	map = new int* [n];
	for (int i = 0; i < n; i++) {
		map[i] = new int[n];
		scanf("%c", &c);
		for (int j = 0, num; j < n; j++) {
			scanf("%c", &c);
			if (c == '#') {
				map[i][j] = 0;
			}
			else {
				num = c - '0';
				map[i][j] = num;
			}
		}
	}

	if (n == 1 || n == 2) {
		printf("0");
		return 0;
	}

	vertex_check();

	playGame();

	printf("%d", sum());


	return 0;
}