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

문제

문제 바로가기> BOJ16946번: 벽 부수고 이동하기 4

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

 

풀이

매번 벽을 만날 때마다 dfs 혹은 bfs 탐색을 진행하면, 복잡도가 O(N^2*M^2)이고,

N과 M 은 최대 1000이므로, 시간초과가 발생한다!

 

이동 가능한 곳의 영역을 미리 체크해 놓는다면, 시간 복잡도를 O(N^M)으로 줄일 수 있다.

예를 들어 예제 2번의 경우,

4 5
11001
00111
01010
10101

다음과 같이 이동가능한 영역의 size?를 미리 체크해 놓는다.

00220
33000
30101
01010

이렇게 해주면, 각 벽에서 이동할 수 있는 곳은 4방향의 값을 더해준 값이다.
이 때, 같은 영역이 중복으로 더해지는 경우를 피하기 위해, 
( ex) (1,1) 과 (2,0)은 같은 영역이므로, (2,1)에서 한번만 더해줘야 함. )
영역 별 번호(num)를 지정해주었다. 이미 사용한 영역이라면 다시 더해주지 않는다!

 

#include<iostream>
#include<string>
#include<queue>
#define MAX 1001
#define MAX2 1000001
#define MOD 10
using namespace std;

struct DATA{int num, cnt;};
queue<int> q;

int N, M;
int map[MAX][MAX];
DATA zero[MAX][MAX];

bool isused[MAX2];
bool visited[MAX][MAX];

int dy[] = {-1,1,0,0}; // 상하좌우
int dx[] = {0,0,-1,1};

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

    string line;
    for(int i=0; i<N; i++){
        cin >> line;
        for(int j=0; j<M; j++) map[i][j] = line[j]-'0';
    }
}

int check_zero_area(int y, int x){ // 이동 가능 영역 크기 반환
    visited[y][x] = true;
    int cnt = 1; // 이동 가능 영역 
    for(int d=0; d<4; d++){
        int ny = y+dy[d];
        int nx = x+dx[d];
        if(ny<0 || ny>=N || nx<0 || nx>=M) continue;
        if(map[ny][nx] || visited[ny][nx]) continue;
        cnt+=check_zero_area(ny, nx);
    }
    return cnt;
}

void mark_zero_area(int y, int x, int num, int cnt){ // 이동 가능 영역 크기 표시
    zero[y][x] = {num, cnt};
    for(int d=0; d<4; d++){
        int ny = y+dy[d];
        int nx = x+dx[d];
        if(ny<0 || ny>=N || nx<0 || nx>=M) continue;
        if(map[ny][nx] || zero[ny][nx].cnt) continue;
        mark_zero_area(ny, nx, num, cnt);
    }
}

void solution(){
    int num = 0; // group 번호
    for(int y=0; y<N; y++){
        for(int x=0; x<M; x++){
            if(map[y][x]==0 && !visited[y][x]) {
                mark_zero_area(y, x, ++num, check_zero_area(y,x));
            }
        }
    }
}

void output(){
    int res, ny, nx;
    for(int y=0; y<N; y++){
        for(int x=0; x<M; x++){
            if(map[y][x]){
                res = 1; // 자기 위치도 칸에 포함
                for(int d=0; d<4; d++){ // 현위치를 기준으로 4 방향 확인
                    ny = y+dy[d];
                    nx = x+dx[d];
                    if(ny<0 || ny>=N || nx<0 || nx>=M || isused[zero[ny][nx].num]) continue; // 범위를 벗어나는 경우, 이미 체크한 영역인 경우
                    isused[zero[ny][nx].num] = true; // 영역 체크
                    q.push(zero[ny][nx].num);
                    res+=zero[ny][nx].cnt;
                } 
                while(!q.empty()){ // 다음에 사용하기 위해
                    isused[q.front()] = false;
                    q.pop();
                }
                cout << res%MOD; // 이동할 수 있는 칸의 개수를 10으로 나눈 나머지 출력
            }
            else cout << 0;
        }
        cout << "\n";
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    input();
    solution();
    output();
}