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

문제

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

걸린 시간

01 : 25 : 38

풀이

C++

#include <bits/stdc++.h>
#define INF 1e9
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int n, m;
int dy[4] = {-1, 1, 0, 0};
int dx[4] = {0, 0, -1, 1};
vector<vector<int>> Map, adj, visited;
vector<pair<int, int>> wall, road;

void bfs(int y, int x, int num){
    vector<pair<int, int>> tmp;
    queue<pair<int, int>> q;
    tmp.push_back(make_pair(y, x));
    q.push(make_pair(y, x));
    visited[y][x] = num;
    while(!q.empty()){
        int cy = q.front().first;
        int cx = q.front().second;
        q.pop();
        for(int i = 0; i < 4; i++){
            int ny = cy+dy[i];
            int nx = cx+dx[i];
            if(0 <= ny && ny < n && 0 <= nx && nx < m){
                if(!visited[ny][nx] && Map[ny][nx] != 1){
                    visited[ny][nx] = num;
                    q.push(make_pair(ny, nx));
                    tmp.push_back(make_pair(ny, nx));
                }
            }
        }
    }
    for(int i = 0; i < tmp.size(); i++){
        int cy = tmp[i].first;
        int cx = tmp[i].second;
        adj[cy][cx] = tmp.size();
    }
}

void divideArea(){
    int num = 1;
    for(int i = 0; i < road.size(); i++){
        int y = road[i].first;
        int x = road[i].second;
        if(!visited[y][x]){
            bfs(y, x, num);
            num++;
        }
    }
}

void countMove(){
    for(int i = 0; i < wall.size(); i++){
        int y = wall[i].first;
        int x = wall[i].second;
        set<int> s;
        for(int j = 0; j < 4; j++){
            int ny = y+dy[j];
            int nx = x+dx[j];
            if(0 <= ny && ny < n && 0 <= nx && nx < m){
                if(Map[ny][nx] != 1){
                    if(s.find(visited[ny][nx]) == s.end()){
                        Map[y][x] += adj[ny][nx];
                        s.insert(visited[ny][nx]);
                    }
                }
            }
        }
        Map[y][x] %= 10;
    }
}

int main(){
    scanf("%d %d", &n, &m);
    Map.resize(n, vector<int>(m));
    adj.resize(n, vector<int>(m, 0));
    visited.resize(n, vector<int>(m, 0));
    for(int y = 0; y < n; y++)
        for(int x = 0; x < m; x++){
            scanf("%1d", &Map[y][x]);
            if(Map[y][x] == 1)
                wall.push_back(make_pair(y, x));
            else
                road.push_back(make_pair(y, x));
        }
    divideArea();
    countMove();
    for(int y = 0; y < n; y++){
        for(int x = 0; x < m; x++)
            printf("%d", Map[y][x]);
        printf("\n");
    }
    return 0;
}

벽의 개수만큼 bfs 를 모두 돌리면 시간초과가 발생한다.

이동할 수 있는 공간을 인접한 영역별로 분리하고, 같은 영역의 모든 좌표의 값을 현재 영역의 원소 개수로 초기화해 둔다.

그리고 벽마다 상하좌우로 다른 영역의 값들을 모아 10으로 나눈 나머지를 저장해 주면 제한 시간 안에 통과할 수 있다.

제출 시 런타임 에러를 몇 번 받았는데 함수의 반환형을 int 로 해 두고 아무런 값도 리턴하지 않은 것이 원인이었다.