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

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

문제 요약

문제

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 변을 공유할 때, 인접하다고 한다.

각각의 벽에 대해서 다음을 구해보려고 한다.

• 벽을 부수고 이동할 수 있는 곳으로 변경한다.
• 그 위치에서 이동할 수 있는 칸의 개수를 세어본다.

한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.

사용 알고리즘

bfs

입출력

• 입력: 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다.
• 출력: 맵의 형태로 정답을 출력한다. 원래 빈 칸인 곳은 0을 출력하고, 벽인 곳은 이동할 수 있는 칸의 개수를 10으로 나눈 나머지를 출력한다. ``` 예제1

입력 3 3 101 010 101 출력 303 050 303

## 풀이
일단 먼저 벽을 부시지 않은 상태에서 인접한 이동가능한 공간이 몇칸인지 개수를 센다. 그 공간 덩어리에 키값을 주고 공간의 크기를 밸류값으로 하여 해시에 저장하고 맵에는 0대신에 키값으로 대체한다. 모두 끝난 뒤 모든 벽에 대하여 인접한 공간의 키값을 가져와 몇칸인지 구하여 더하면 된다.

## 어려웠던 점
복붙할때 고쳐서 붙여넣어야 하는것들을 그냥 넘어가서 틀리는 경우가 많았다. 인접한 공간의 키값을 구하여 더할때 상하좌우에서 키값이 겹치는게 있으면 한번만 더해주어야 하는데 다 더해서 틀렸다. 

## 배운 점 / 느낀 점
굉장히 많은 자료구조를 사용하였다. 그냥 map은 해시 구조가 아니라서 속도가 느리고 unordered_map을 사용하여야 속도가 빠르다는 것을 알았다. 실제로 속도가 25% 이상 빨라 졌다. 

## 전체 코드
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <queue>
#include <set>
using namespace std;

int n, m;
vector<vector<int>> ma;
queue<pair<int,int>> q;
unordered_map<int, int> c;

void bfs(int k, int y, int x){
    q = queue<pair<int,int>>();
    q.push({y,x});
    while(!q.empty()){
        pair<int,int> node = q.front();
        q.pop();
        if(ma[node.first][node.second] != 0){
            continue;
        }
        ma[node.first][node.second] = k;
        c[k]++;
        if(node.first != 0){
            q.push({node.first-1, node.second});
        }
        if(node.first != n-1){
            q.push({node.first+1, node.second});
        }
        if(node.second != 0){
            q.push({node.first, node.second-1});
        }
        if(node.second != m-1){
            q.push({node.first, node.second+1});
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n >> m;

    ma = vector<vector<int>>(n, vector<int>(m));

    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            char chr;
            cin >> chr;
            ma[i][j] = chr-'0';
        }
    }

    for(int i = 0, k = 2; i < n; i++){
        for(int j = 0; j < m; j++){
            if(ma[i][j] == 0){
                bfs(k++, i, j);
            }
        }
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(ma[i][j] == 1){
                int r = 1;
                set<int> a = set<int>();
                if(i != 0){
                    a.insert(ma[i-1][j]);
                }
                if(i != n-1){
                    a.insert(ma[i+1][j]);
                }
                if(j != 0){
                    a.insert(ma[i][j-1]);
                }
                if(j != m-1){
                    a.insert(ma[i][j+1]);
                }
                for(int h : a){
                    r += c[h];
                }
                cout << r%10;
            }
            else{
                cout << 0;
            }
        }
        cout << "\n";
    }
    return 0;
}