[백준/Baekjoon] 16946 벽 부수고 이동하기 4 C++ :: BFS

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

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

---

1. Logic

여러가지 방법으로 시도해봤다. 시도한 방법은

1. DFS : DFS로 벽인 부분에서 이동할 수 있는 공간의 크기를 세서 저장했다. 100만개 탐색을 100만번 하니 당연히 터질 수 밖에. 그래서 DP로 접근했다.

2. DP : 한 정점에서 다른 정점으로 가는 방법을 DP로 하면 방향이 일정하기 때문에 값이 구해지지만 이번 문제는 상하좌우를 판단해야 하기 때문에 (0,0)에서 (n-1, n-1)로 가는 방향은 잘 나오지만 반대방향이나 다른 방향은 값이 이상하게 나왔다. 그래서 BFS로 넘어갓따.

3. BFS : 기본 BFS를 돌았다. 당연히 얘도 O(N*M*(V+E))만큼 탐색해버리니 시간초과

4. 붙어있는 0번끼리 섹션을 묶은 후 BFS : 벽(1)에서 시작해서 모든 이동가능한 공간(0)을 탐색하면 사실상 완탐이기 때문에 시간초과가 난다. 그래서 붙어있는 0끼리 BFS를 돌면서 1~n*n까지의 번호를 매겨주고 갯수를 구해놓는다. 이후 1번에서 상하좌우를 탐색해서 붙어있는 0의 번호의 갯수를 더해준다.

---

2. Code

#include<bits/stdc++.h>

using namespace std;

int n, m;

int distinguish = 1;

char arr[1001][1001];
int changeArr[1001][1001];
int res[1001][1001];
int sizeToArea[1000001];

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};

void bfs(int yy, int xx) {
    queue<pair<int, int>> q;
    
    q.push({yy, xx});
    changeArr[yy][xx] = distinguish;
    
    int cnt = 0;
    
    while(!q.empty()) {
        int x = q.front().second;
        int y = q.front().first;
        
        q.pop();
        
        cnt++;
        
        for(int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if(nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
            if(arr[ny][nx] == '1') continue;
            if(changeArr[ny][nx] > 0) continue;
            
            changeArr[ny][nx] = distinguish;
            q.push({ny, nx});
        }
    }
    
    sizeToArea[distinguish] = cnt;
    distinguish++;
}

void solve(int y, int x) {
    int cnt = 1;
    vector<int> check;
    for(int i = 0; i < 4; i++) {
        bool con = false;
        int nx = x + dx[i];
        int ny = y + dy[i];
        
        if(nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
        
        for(auto &a : check) {
            if(a == changeArr[ny][nx]) {
                con = true;
                break;
            }
        }
        if(con) continue;
        check.push_back(changeArr[ny][nx]);
        cnt += sizeToArea[changeArr[ny][nx]];
    }
    res[y][x] = cnt;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cin >> n >> m;
    
    for(int i = 0; i < n; i++) {
        string str;
        cin >> str;
        for(int j = 0; j < m; j++) {
            arr[i][j] = str[j];
        }
    }
    
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(arr[i][j] == '1') continue;
            if(changeArr[i][j] > 0) continue;
            bfs(i, j);
        }
    }
    
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(arr[i][j] == '0') continue;
            solve(i, j);
        }
    }
    
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            cout << res[i][j] % 10;
        }
        cout << '\n';
    }
}

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐