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

문제 링크: https://www.acmicpc.net/problem/16946

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

<문제 풀이>

각각의 벽에 대해서 BFS를 호출하면 벽 찾는데 O(N * M), BFS 호출하는데 O(N + M) 이므로 총 O( (N+M) * N*M )이 걸리게 된다.

 

벽을 부수었을 때 이동할 수 있는 곳은 벽을 기준으로 상하좌우의 0으로 이루어진 영역들이므로 0에 대해서 BFS를 1회 호출해서 영역을 구하고, 각 벽에 대해서 상하좌우 영역의 크기만 계산하면 O(N * M)에 해결할 수 있다.

 

<C++ 소스 코드>

#include<iostream>
#include<queue>
#include<utility>
using namespace std;
 
#define X first
#define Y second
 
int N, M;
int board[1000][1000];
int visited[1000][1000];
int res[1000][1000];
int connected[1000001];
bool useC[1000001];
const int dx[4] = { 0, 0, 1, -1 };
const int dy[4] = { 1, -1, 0, 0 };
void bfs() {
    int flag = 1;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (board[i][j] || visited[i][j]) continue;
            queue<pair<int, int> > Q;
            Q.push({ i, j });
            visited[i][j] = flag;
            int cnt = 1;
            while (!Q.empty()) {
                auto cur = Q.front(); Q.pop();
                for (int dir = 0; dir < 4; dir++) {
                    int nx = cur.X + dx[dir];
                    int ny = cur.Y + dy[dir];
                    if (nx < 0 || ny < 0 || nx >= N || ny >= M)continue;
                    if (board[nx][ny] || visited[nx][ny])continue;
                    Q.push({ nx, ny });
                    visited[nx][ny] = flag;
                    cnt++;
                }    
            }
            connected[flag] = cnt;
            flag++;
            
        }
    }
}
 
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            char c; cin >> c;
            board[i][j] = c - '0';
        }
    }
    bfs();
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (board[i][j] == 1) {
                res[i][j] = 1;
                for (int dir = 0; dir < 4; dir++) {
                    int nx = i + dx[dir];
                    int ny = j + dy[dir];
                    if (nx < 0 || ny < 0 || nx >= N || ny >= M)continue;
                    if (board[nx][ny] || useC[visited[nx][ny]]) continue;
                    useC[visited[nx][ny]] = true;
                    res[i][j] = (res[i][j] + connected[visited[nx][ny]]) % 10;
                }
                for (int dir = 0; dir < 4; dir++) {
                    int nx = i + dx[dir];
                    int ny = j + dy[dir];
                    if (nx < 0 || ny < 0 || nx >= N || ny >= M)continue;
                    useC[visited[nx][ny]] = false;
                }
 
            }
        }
    }
    
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cout << res[i][j];
        }
        cout << '\n';
    }
 
    return 0;
}