BOJ 2140 지뢰찾기

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

 

우선 생각할 수 있는 건 지뢰의 최대개수를 알아내는 거기 때문에,

가생이와 그 맞닿아 있는 부분 빼고 안쪽은 전부 지뢰로 처리하면 되는 걸 생각해낼 수 있었다.

그럼 이제 가생이의 숫자들을 보고, 바로 안쪽 부분에 지뢰가 있는지 없는지를 계산해주면 된다.

 

가생이 바로 안쪽 #이 있는 부분을 돈다.

# 주위 8구역을 본다.

우선 0이 나온다면, 주위 반경(8구역)에 지뢰가 하나도 있으면 안된다.

이 경우, 아무런 처리도 하지 않고 넘어간다.

 

그리고 주변 구역들이 모두 0이 아니라면, 지뢰를 놓을 수 있다는 뜻이다. 

정답을 + 1 해준다.

그리고, 지뢰를 놨으므로, 주변 8구역 (물론 지뢰가 있는 부분이 아닌, 숫자가 있는 가생이 부분)에 -1을 다 해준다.

 

이렇게 해서 돈 다음, 첫 문단에서 말한것 처럼 안쪽은 전부 지뢰로 보면 되기 때문에,

n-4가 0보다 크다면 (양쪽 가생이와 바로 맞닿아있는 #을 제외한 안쪽 정사각형)

정답에 (n-4) * (n-4)를 더해준다.

 

++ 처음 문제를 풀 때, 안쪽 구역들 전부 지뢰와 0이 나오면 주위반경에 지뢰가 없다는 것 까진 생각했지만, 

지뢰를 놔줄 때 주변 구역에 -1을 해줘야 한다는 것 까진 떠올리지 못했었다. 

그래서 #인 부분을 우선 전부 지뢰라고 가정하고, 0이 나오는 좌표를 저장해놓은 다음, 0이 나오는 부분의 주위만 전부 지뢰가 없게 만든 후, 지뢰를 세는 방식으로 했었다. (https://www.acmicpc.net/source/share/fa6656fbc83e4f898feaed96dc060f7b)

다른 분들의 코드를 보고 많이 생각하고 나서 맞출 수 있었다.

본 글중 최고로 좋았던 건, 반례를 공유해주신것.

반례

 

5

11211

1###1

2###2

1###1

11211

 

ans : 5

 

 

// 정답코드
#include <bits/stdc++.h>
using namespace std;
int n;
int a[104][104];
string s;
int dirY[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dirX[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
int ans = 0;

void print()
{
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cout << a[i][j] << " ";
        }
        cout << "\n";
    }
}

void near8(int y, int x)
{
    bool zeroFlag = false;
    for (int i = 0; i < 8; i++)
    {
        int nextY = y + dirY[i];
        int nextX = x + dirX[i];
        if (a[nextY][nextX] == 0)
        {
            zeroFlag = true;
            break;
        }
    }
    if (!zeroFlag)
    {
        for (int i = 0; i < 8; i++)
        {
            int nextY = y + dirY[i];
            int nextX = x + dirX[i];
            if (a[nextY][nextX] > 0)
            {
                a[nextY][nextX]--;
            }
        }
        ans++;
    }
}

int main()
{
    // n-4 * n-4의 공간은 무조건 지뢰가 있다.
    // -1 : 아직 모름(#)
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> s;
        for (int j = 0; j < s.size(); j++)
        {
            if (s[j] == '#')
            {
                a[i][j] = -1;
            }
            else
            {
                a[i][j] = s[j] - '0';
            }
        }
    }

    for (int i = 1; i < n - 1; i++)
    {
        near8(1, i);     // 위
        near8(n - 2, i); // 아래
        near8(i, 1);     // 왼쪽
        near8(i, n - 2); // 오른쪽
    }

    if (n >= 4)
    {
        ans += (n - 4) * (n - 4);
    }

    // print();

    cout << ans << "\n";
    return 0;
}

/*
5
11211
1###1
2###2
1###1
11211
*/