[백준] 10711번 모래성 (C++)

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

 

 

이 문제는 H X W 격자판이 주어지고 격자에 모래성과 빈칸이 주어졌을때 파도가 계속 칠때 언제까지 수렴해서 모래성이 없어지지 않은지 출력하는 문제이다.

 

먼저 모래성은 1부터 9사이의 정수값이 주어지고 모래성을 기준으로 상하좌우 대각선 총 8방향으로 모래성이 쌓여있지 않은 부분의 개수가 자기 모래성의 튼튼함의 개수보다 많으면 이는 모래성이 파도에 없어질 수 있다는 의미이다

 

 

처음에는 bfs를 사용하여 cnt를 증가시키며 없어지는 좌표에 대해서 다시 bfs함수를 돌리는 것으로 구현을 했는데 이때 시간초과가나서 다른 방법을 생각해냈어야 했다.

 

이를 해결하기 위해서 bfs를 사용하여 모래를 큐에 넣어주었다. 이후 8방향으로 살펴서 만약 모래성이 있는 경우 -1씩 감소시켰다 이때 만만약 모래성이 0이되서 빈칸이 되는경우 그 좌표를 다시 큐에 넣고 탐색을 하였다.

 

정답코드

#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, M, cnt;
char Map[1001][1001];
int graph[1001][1001];
queue<pii> q;

bool check(int x, int y) {
    if(x >= 0 && x < N && y >= 0 && y < M) return true;
    else return false;
}

void bfs() {
    while(!q.empty()) {
        int sz = q.size();

        for(int i = 0; i < sz; i++) {
            int x = q.front().first;
            int y = q.front().second;
            q.pop();

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

                if(!check(nx, ny)) continue;

                if(graph[nx][ny] > 0) {
                    graph[nx][ny] -= 1;

                    if(graph[nx][ny] == 0) q.push({nx, ny});
                }
            }
        }
        cnt++;
    }
}

void solve() {
    bfs();

    cout << cnt - 1;
}

void input() {
    cin >> N >> M;

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

            if(Map[i][j] == '.') {
                graph[i][j] = 0;
                q.push({i, j});
            }
            else graph[i][j] = Map[i][j] - '0';
        }
    }
}

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

    input();
    solve();
}

 

 

회고록

문제를 해결하기 위해 bfs를 여러번 돌리는것을 생각했는데 무조건 시간초과가난다고 생각해서 set을 사용해서 최적화를 했지만 bfs를 여러번 돌리는 것이 너무 시간을 잡아먹었다.