백준[16946] 벽 부수고 이동하기 4

문제 설명

문제 링크

http://icpc.me/16946

16946번: 벽 부수고 이동하기 4

풀이

dfs를 이용하여 풀 수 있다.

모든 1에 대해서 dfs를 돌며 인접한 0이 몇 개인지 센다면 한번 dfs를 돌 때 O(NM)이고 dfs를 NM번 돌릴 수 있기 때문에 O(N^2M^2)이 돼서 시간이 터질 것이다.

그렇기 때문에 인접한 0의 개수들을 미리 구해놓고, 1이 나올 때 상하좌우에 붙어있는 인접한 0의 개수만 세주면 된다.

상하좌우에 붙어있는 그룹이 같은 그룹인지 아닌지 체크도 해줘야 한다.

코드

#include <cstdio>
#include <vector>

using namespace std;

const int N = 1003;
int adj[N][N], adjZero[N][N][2];
int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
bool visited[N][N], groups[N * N];
int n, m, cnt, g = 1;
vector<pair<int, int>> v;

void dfs(int r, int c) {
    cnt++;
    visited[r][c] = true;
    v.push_back({r, c});
    for (int i = 0; i < 4; i++) {
        int nr = r + dir[i][0];
        int nc = c + dir[i][1];
        if (nr >= n || nr < 0 || nc >= m || nc < 0) continue;
        if (visited[nr][nc] || adj[nr][nc]) continue;
        dfs(nr, nc);
    }
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) scanf("%1d", &adj[i][j]);
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (!adj[i][j] && !visited[i][j]) {
                dfs(i, j);
                for (auto [a, b] : v) {
                    adjZero[a][b][0] = cnt;
                    adjZero[a][b][1] = g;
                }
                v.clear();
                cnt = 0;
                g++;
            }
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (adj[i][j]) {
                int ret = 0;
                for (int d = 0; d < 4; d++) {
                    int nr = i + dir[d][0];
                    int nc = j + dir[d][1];
                    if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
                    if (groups[adjZero[nr][nc][1]] || adj[nr][nc]) continue;
                    ret += adjZero[nr][nc][0];
                    groups[adjZero[nr][nc][1]] = true;
                }
                for (int d = 0; d < 4; d++) {
                    int nr = i + dir[d][0];
                    int nc = j + dir[d][1];
                    if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
                    groups[adjZero[nr][nc][1]] = false;
                }
                printf("%d", (ret  + 1) % 10);
            } else {
                printf("0");
            }
        }
        printf("\n");
    }
}