BOJ 3064 : Minesweeper

• 문제 링크 : boj.kr/3064
• 난이도 : G4
• 태그 : 구현, 그리디

3064번: Minesweeper

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

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

    int T;
    cin >> T;
    while(T--) {
        int n;
        cin >> n;
        vector<vector<int>> board(n, vector<int>(n));
        for(int i = 0; i < n; i++) {
            string s;
            cin >> s;
            for(int j = 0; j < n; j++) {
                if(s[j] == '#') {
                    board[i][j] = -1;
                }
                else {
                    board[i][j] = s[j] - '0';
                }
            }
        }
        int ans = 0;
        for(int i = 1; i < n-1; i++) {
            for(int j = 1; j < n-1; j++) {
                int m = 3;
                for(int dx = -1; dx <= 1; dx++) {
                    for(int dy = -1; dy <= 1; dy++) {
                        if(dx == 0 && dy == 0) continue;
                        if(board[i+dx][j+dy] >= 0) {
                            m = min(m, board[i+dx][j+dy]);
                        }
                    }
                }
                if(m > 0) {
                    ans++;
                    for(int dx = -1; dx <= 1; dx++) {
                        for(int dy = -1; dy <= 1; dy++) {
                            if(dx == 0 && dy == 0) continue;
                            if(board[i+dx][j+dy] >= 0) {
                                board[i+dx][j+dy]--;
                            }
                        }
                    }
                }
            }
        }
        cout << ans << "\n";
    }
    return 0;
}

---

풀이

왼쪽 위 모서리부터 글을 읽는 순서대로 지뢰가 놓여질 수 있는지 확인한다.

순서대로 확인할 경우 주변의 8칸 중 어느 하나의 모서리는 현재의 칸만 영향을 줄 수 있게 된다.

1	1	1	0	0	0
2	a	b	c	d	0
3	e	f	g	h	1
3	i	j	k	l	1
2	m	n	o	p	1
1	1	2	1	1	0

 

위의 표가 예시로 주어졌다고 해보자. (알파벳은 탐색 순서이다.)

e를 탐색할 때에는 a는 이미 탐색했으므로 왼쪽 위의 2에는 e만이 영향을 줄 수 있는 상태이다. 따라서 주변의 8칸에 숫자가 적혀있는 칸 중 최소가 0이 아니라면 해당 칸에는 지뢰가 있음이 보장된다. 

주변의 8칸에 숫자가 없다면 그건 어떻게 되든 상관이 없는 칸이니 지뢰의 수를 최대화하기 위해 지뢰가 있다고 가정하면 된다.