[백준 16946] 벽 부수고 이동하기 4 (C++)

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

BFS

---

우선 bfs를 수행하면서 연속해서 비어있는 칸의 묶음마다 집합의 번호를 매겨주고 집합의 번호에 따라서 집합의 크기를 저장했다.

setMap[][] 배열에는 해당 칸의 집합의 번호를 넣어준다.

setcount 변수는 bfs를 수행하는 횟수만큼 집합이 생길 것이므로 bfs가 끝날 때마다 1씩 더해줘서 집합의 번호를 가지고 있는다.

setnums[] 배열에는 집합의 번호에 따른 집합의 크기를 저장한다. 집합의 크기는 bfs를 수행할 때마다 방문하는 칸의 개수가 된다.

 

여기까지가 답을 구하기 위한 preset이다.

 

이제 Map의값이 0이 아닌 모든 지점을 방문하면서 다음의 과정을 수행한다.

자신의 벽을 부술 수 있기 때문에 기본값 1을 가진다.

그리고 자신의 상하좌우 칸을 살펴보면서 이전에 방문한 집합인지 체크해준다.

방문하지 않았다면 해당 집합의 값을 더해주고 방문한 배열에 추가해준다.

만약 이전에 방문한 적이 있다면 해당 집합의 크기를 이미 더해준 상태이므로 다음 인접 칸으로 넘어간다.

방문한 배열의 크기는 최대 4이고 순차적으로 증가하기 때문에 전체 횟수는 총 10번 돌게 된다.

따라서 시간복잡도는 O(10 * N*M)이 된다.

 

처음에 시간초과가 났었던 이유는 bfs를 수행하면서 매번 visited[1001][1001] 배열을 초기화 시켜줬기 때문이다.

memset이 빠르긴하지만 2차원 배열 초기화는 N^2이라고 생각을 하고 풀었어야 했는데 생각하지 못했다.

그리고 visited[][]배열을 만들 필요가 없었는데.. 바로 setMap[][] 배열이 이미 방문한 칸의 집합을 번호를 가지고 있기 때문에 visited배열을 따로 만들어 줄 필요가 없다. 기초적인 실수를 해서 슬펐다.

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#define fasti ios_base::sync_with_stdio(false); cin.tie(0);
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 1e9+7
#define pii pair<int, int>
 
typedef long long ll;
// typedef pair<int, int> pii;
 
using namespace std;
 
int N, M;
int Map[1001][1001];
int setMap[1001][1001];
int result[1001][1001];
int setnums[1000001];
 
int setcount = 1;
int dr[4] = {0, 0, 1, -1}, dc[4] = {1, -1, 0, 0};
 
void input(){
    cin >> N >> M;
    string str;
    for(int i = 0; i < N; i++){
        cin >> str;
        for(int j = 0; j < M; j++){
            Map[i][j] = str[j] - '0';
        }
    }
}
 
void bfs(int r, int c){
    queue<pii > que;
    que.push({r, c});
    setMap[r][c] = setcount;
    
    int cnt = 0;
    
    while(!que.empty()){
        pii now = que.front();
        que.pop();
        cnt++;
        
        for(int k = 0; k < 4; k++){
            int nr = now.first+ dr[k];
            int nc = now.second + dc[k];
            
            if(nr < 0 || nc < 0 || nr >= N || nc >= M) continue;
            if(Map[nr][nc] > 0 || setMap[nr][nc]) continue;
            setMap[nr][nc] = setcount;
            que.push({nr, nc});
        }
    }
    
    setnums[setcount++] = cnt;
}
 
void solve(){
    for(int r = 0; r < N; r++){
        for(int c = 0; c < M; c++){
            if(Map[r][c] != 0 || setMap[r][c] > 0) continue;
            bfs(r, c);
        }
    }
    
    for(int r = 0; r < N; r++){
        for(int c = 0; c < M; c++){
            if(Map[r][c] > 0){
                int cnt = 1;
                vector<int> check;
                for(int k = 0; k < 4; k++){
                    bool con = false;
                    int nr = r + dr[k];
                    int nc = c + dc[k];
                    
                    if(nr < 0 || nc < 0 || nr >= N || nc >= M) continue;
                    for(auto &w : check){
                        if(w == setMap[nr][nc]){
                            con = true;
                            break;
                        }
                    }
                    check.push_back(setMap[nr][nc]);
                    if(con) continue;
                    cnt += setnums[setMap[nr][nc]];
                }
                result[r][c] = cnt;
            }
        }
    }
    
    for(int r = 0; r < N; r++){
        for(int c = 0; c < M; c++){
            cout << result[r][c]%10;
        }
        cout << "\n";
    }
}
 
int main(){
    fastio
    input();
    solve();
    
    return 0;
}