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

문제 링크

성공 여부(걸린 시간): 성공(1시간쯤)

아이디어

각 벽을 부수고 해당 위치부터 출발해서 BFS를 돌았을때

몇개의 영역을 지니는지에 대해서 계산해서 출력해준다.

그런데 그걸 단순히 전부돌때마다 BFS를 해서 더해서 해당 위치의 벽을 부수고 갈 수 있는 칸 수를 구하면

최악의 경우 BFS를 최대 100만번을 해야하고 그렇게 했을때는 시간초과가 날 것이라고 생각이된다.
그렇기 때문에 각 0으로(벽이 아닌) 연결되어있는 영역에 대해서 그룹을 지정하고 넓이를 그룹별로 저장해준다.

 

그럼 나중에 벽에 대해서 구할때
상하좌우에 위치하는 그룹의 너비의 합을 구해서 10으로 나눠서 출력해주면 된다.

풀이 코드

#include<iostream>
#include<queue>
#include<map>
#include<set>
using namespace std;

int map_arr[1001][1001] = { {0,}, };
int group_arr[1001][1001] = { {0,}, };
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
int N = 0, M = 0;
int group = 1;
map<int, int> m;

bool can_go(int x, int y) {
    return x >= 0 && y >= 0 && x < N && y < M;
}

void bfs(int x, int y) {
    queue<pair<int, int>> q;
    q.push({x, y});
    group_arr[x][y] = group;
    int area = 0;
    while (!q.empty()) {
        pair<int, int> cur = q.front();
        q.pop();
        area++;
        for (int dir = 0; dir < 4; dir++) {
            int mx = cur.first + dx[dir];
            int my = cur.second + dy[dir];
            if (can_go(mx, my) && group_arr[mx][my]==0 && map_arr[mx][my] == 0) {
                q.push({ mx, my });
                group_arr[mx][my] = group;
            }
        }
    }
    m[group] = area;
    group++;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);    
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        string input;
        cin >> input;
        for (int j = 0; j < M; j++) {
            map_arr[i][j] = input.at(j) - '0';
        }
    }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (group_arr[i][j] == 0 && map_arr[i][j] == 0) {
                bfs(i, j);
            }
        }
    }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            int sum = 0;
            if (map_arr[i][j] == 1) {
                sum++;
                set<int> groups;
                for (int dir = 0; dir < 4; dir++) {
                    int mx = i + dx[dir];
                    int my = j + dy[dir];
                    if (can_go(mx, my) && map_arr[mx][my]==0 ) {
                        groups.insert(group_arr[mx][my]);
                    }
                }
                for (int x: groups) {
                    sum += m[x];
                }
                sum %= 10;
            }
            cout << sum;
        }
        cout << "\n";
    }
    return 0;
}