1868번 파핑파핑 지뢰찾기

풀이방법)

나는 먼저 0인 좌표(주변의 지뢰가 없는곳)를 찾아 탐색을 해서 먼저 방문영역을 체크해두기로했다.

 - 여기서 탐색을 한다는 것은 한번의클릭으로 모두 제거되는 것이기 때문에 카운트를 하나로 취급해준다.

그리고 모든 좌표를 탐색하면서 방문이 안된 녀석들은 주변에 지뢰가 있는 것이기때문에 하나씩 카운트를 세준다.

1. 모든좌표마다 8방향 주변에 지뢰개수를 파악해서 그 개수를 표시해주는 맵을 새로 만든다.

2. 새로운 맵에서 0인 좌표부터 bfs 탐색을 시작해서 주변의 영역을 방문표시해둔다. 

3. 인접한 0들은 모두 2번에서 없어진 것이고, 나머지 방문안된 0도 bfs탐색을 하면서 주변영역을 방문표시해준다.

4. bfs탐색을 한번할때마다 카운트를 1씩증가한다.

5. 최종적으로 원래 맵을 돌면서 방문안된 좌표는 하나씩 카운트를 세주고 3번에서 구한 카운트와 합산하면 정답이다.

 

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
int changemap[301][301] = { 1, };
char basemap[301][301];
int visit[301][301];
int n;
int dx[] = { -1,-1,-1,0,1,1,1,0 };
int dy[] = { -1, 0, 1, 1,1,0,-1,-1 };
queue< pair<int, int> > q;
bool isInmap(int x, int y)
{
    if (x <0 || x >n - 1 || y<0 || y>n - 1)
    {
        return false;
    }
    else
        return true;
}
void Change()
{
 
    for (int x = 0; x<n; x++)
    {
        for (int y = 0; y<n; y++)
        {
            //각 좌표마다 8방향에서 지뢰개수를 채워나간다.
            int cnt = 0;
            if (basemap[x][y] == '*')
            {
                changemap[x][y] = -1;
                continue;
            }
            for (int i = 0; i<8; i++)
            {
                int tx = x + dx[i];
                int ty = y + dy[i];
                if (basemap[tx][ty] == '*')
                {
                    cnt++;
                }
            }
            changemap[x][y] = cnt;
 
        }
    }
}
void bfs(int x, int y)
{
    // bfs탐색으로 0인 좌표에서 8방향 값을 visit 체크해준다. 
    int nx, ny, nnx, nny;
    q.push({ x,y });
    while (!q.empty())
    {
        nx = q.front().first;
        ny = q.front().second;
        visit[nx][ny] = 1;
        for (int i = 0; i<8; i++)
        {
            nnx = nx + dx[i];
            nny = ny + dy[i];
            if (!isInmap(nnx, nny))
            {
                continue;
            }
            if (!visit[nnx][nny])
            {
                visit[nnx][nny] = 1; // 방문안된 좌표는 방문처리해준다. 중복 방문표시 예방 
                if (changemap[nnx][nny] == 0)
                {
                    q.push({ nnx,nny });
                }
            }
        }
        q.pop();
    }
}
int main()
{
    int T;
    scanf("%d", &T);
    for (int t = 1; t <= T; t++)
    {
        int ret = 0;
        cin >> n;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                scanf(" %c", &basemap[i][j]);
            }
        }
        Change();
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (changemap[i][j] == 0 && !visit[i][j])
                {
                    bfs(i, j);
                    ret++; // bfs탐색한다면 클릭횟수증가. 
                }
            }
        }
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (changemap[i][j] > 0 && !visit[i][j])
                {
                    ret++;
                }
            }
        }
        printf("#%d %d\n", t, ret);
        memset(visit, 0, sizeof(visit));
    }
}