[BOJ] 2140: 지뢰찾기 (C++)

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

2140번: 지뢰찾기

걸린 시간 : 40분 12초

---

간단한 그리디와 구현 문제이다. 코드는 좀 복잡해 보일 수 있지만 어렵지 않다.

1. 파란색 부분을 처리한다. 꼭짓점 부분이 1이라면 지뢰가 있는 것이고, 0이라면 없는 것이다. 따라서 파란색 부분은 간단하게 처리할 수 있다.
2. 빨간색 부분을 처리한다. 꼭짓점 부분을 제외한 가장자리 모서리 부분이다. 인덱스가 낮은 곳부터 처리하다 보면 각 지점이 결정된다.
   위쪽 모서리를 보자. board[0][i] 의 수를 지뢰의 수 mine이라 하자. board[1][i-1] 과 board[1][i] 는 이미 결정되어 있다. 따라서 board[1][i+1] 은 결정될 수 있다. 왼쪽, 오른쪽, 아래쪽 모서리도 같은 방식으로 모두 결정할 수 있다.
3. 보라색 부분, 즉 가장자리가 아닌 부분은 나와있는 수들에 결정되지 않는다. "최댓값"을 구하라고 했으므로 모두 지뢰가 채워진 것으로 가정한다. 이 때, N 값이 5 이상이어야 보라색 부분이 존재한다. 이 부분의 개수는 N-4 의 제곱이다.
4. 예제는 N이 5 이상일 경우이다. 하지만 문제의 조건은 N이 1 이상이므로 N이 1,2,3,4일 경우는 모두 테스트해보아야 한다. N이 1,2 일 때는 지뢰가 존재할 수 없지만, N이 3일 경우 존재할 수도 하지 않을 수도 있다. 그리고 지금까지의 로직으로 동작하지 않는다. 이 경우를 포함해서 동작하는 알고리즘을 새로 만들기보다는 예외처리해주면 될 것이다.

 

 

#include <bits/stdc++.h>
using namespace std;

int N, ans;
string board[101];

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N;
	for (int i = 0; i < N; i++)
		cin >> board[i];
    // N이 3일 경우 예외처리
	if (N == 3) {
		if (board[0][0] == '1') {
			cout << 1;
			return 0;
		}
		else {
			cout << 0;
			return 0;
		}
	}
	//꼭짓점
	if (board[0][0] == '1') {
		board[1][1] = '*';
		ans++;
	}
	if (board[0][N-1] == '1') {
		board[1][N-2] = '*';
		ans++;
	}
	if (board[N-1][0] == '1') {
		board[N-2][1] = '*';
		ans++;
	}
	if (board[N-1][N-1] == '1') {
		board[N-2][N-2] = '*';
		ans++;
	}
	//모서리
	for (int i = 1; i < N-3; i++) {
		int mine = board[0][i] - '0';
		int cur = 0;
		if (board[1][i-1] == '*') cur++;
		if (board[1][i] == '*') cur++;
		if (mine > cur) {
			board[1][i+1] = '*';
			ans++;
		}
	}
	for (int i = 1; i < N-3; i++) {
		int mine = board[i][0] - '0';
		int cur = 0;
		if (board[i-1][1] == '*') cur++;
		if (board[i][1] == '*') cur++;
		if (mine > cur) {
			board[i+1][1] = '*';
			ans++;
		}
	}
	for (int i = 1; i < N-3; i++) {
		int mine = board[N-1][i] - '0';
		int cur = 0;
		if (board[N-2][i-1] == '*') cur++;
		if (board[N-2][i] == '*') cur++;
		if (mine > cur) {
			board[N-2][i+1] = '*';
			ans++;
		}
	}
	for (int i = 1; i < N-3; i++) {
		int mine = board[i][N-1] - '0';
		int cur = 0;
		if (board[i-1][N-2] == '*') cur++;
		if (board[i][N-2] == '*') cur++;
		if (mine > cur) {
			board[i+1][N-2] = '*';
			ans++;
		}
	}
	if (N > 4)
		ans += (N-4) * (N-4);
	cout << ans;
	return 0;
}