[백준] 2140번 지뢰찾기 (C++)

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

 

 

이 문제는 N X N 격자가 주어지고 바깥쪽 면에 대해서는 숫자가 주어지고 이외에는 지뢰가 있을 수 있는 #칸이 주어진다.

 

문제에서 요구하는 것은 최대개수의 지뢰이며 바깥쪽 숫자가 나타내는 것은 칸을 기준으로 상하좌우 대각선 총 8가지 칸에 지뢰의 개수가 있다는 의미이다. 그렇다면 우리는 불확실성에 대해서 먼저 확실하게 지뢰가 있는 것을 우선으로 찾을 필요가 있다.

 

이때 바깥 대각선 4부분은 지뢰가 겹치는 곳이 한가지이기 때문에 우선적으로 바깥 대각선에 대해 지뢰를 찾으며

그 지뢰를 기준으로 상하좌우 대각선 8방향에 숫자가 있는 경우 1씩 낮춰주어 지뢰 예측 수를 감소시킨다.

 

이후 순차적으로 격자를 탐색하여 숫자를 탐색하여 지뢰를 놓으면 된다 마지막으로 방문했지만 계속 #인 경우 최대 개수의 지뢰를 출력함으로 1을 더한다.

 

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"
#define MAX 1e9

struct coordinate {
    int x;
    int y;
    int r;
};

int dx[] = {-1, 1, 0, 0, 1, -1, -1, 1};
int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};
int N, cnt;
char graph[101][101];
int dp[101][101];
priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>>pq;
bool visited[101][101];
vector<pii> v;

/*
    bfs로 숫자로 탐색하여
*/

void Print() {
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            cout << graph[i][j] << " ";
        }
        cout << endl;
    }

    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            cout << dp[i][j] << " ";
        }
        cout << endl;
    }
}

void bfs(int a, int b) {
    queue<pii> q;
    vector<pii> tmp;
    q.push({a, b});
    int cnt = dp[a][b];

    while(!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();

        for(int i = 0; i < 8; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if(nx < 0 || nx >= N || ny < 0 || ny >= N) continue;

            if(graph[nx][ny] != '#') continue;

            if(cnt - 1 < 0) {
                graph[nx][ny] = '.';
            }
            else {
                graph[nx][ny] = '*';
                tmp.push_back({nx, ny});
            }
        }
    }

    for(auto it : tmp) {        // 만들었던 지뢰에서 상, 하, 좌, 우, 대각선 1씩 줄이기
        int x = it.first;
        int y = it.second;

        for(int i = 0; i < 8; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if(nx < 0 || nx >= N || ny < 0 || ny >= N) continue;

            if(dp[nx][ny] > 0) {        // 지뢰 개수 줄여줘야함
                dp[nx][ny]--;
            }
        }
    }
}

void solve() {
    for(auto it : v) {
        int col = it.first;
        int row = it.second;

        bfs(col, row);
    }

    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            if(graph[i][j] >= 48 && graph[i][j] <= 57) {
                bfs(i, j);
            }
        }
    }

    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            if(graph[i][j] == '*' || graph[i][j] == '#') {
                cnt++;
            }
        }
    }

    cout << cnt << endl;
}


void input() {
    cin >> N;

    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            cin >> graph[i][j];

            if((i == 0 || i == N-1) && (j == 0 || j == N-1)) {
                v.push_back({i, j});
            }

            if(graph[i][j] != '#') {
                dp[i][j] = graph[i][j] - '0';
            }
        }
    }
}

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

    input();
    solve();
}

 

 

회고록

시간이 굉장히 오래 걸렸던 문제... 또한 문제의 접근을 저렇게 안하고 처음엔 대각선 바깥 방향을 탐색한 이후 미리 우선순위 큐에 숫자와 좌표를 넣어서 탐색하는 것으로 하였다. 그 이유는 숫자가 높을 수록 지뢰를 더 많이 발견할 수 있다는 안일한 생각에 그랬던것 같다.