백준16946

이 문제를 처음 보았을 때는, 그저 단순하게 벽의 좌표들을 vector에 저장해놓고 각각을 기준으로 bfs를 이용하여 갈 수 있는 칸의 수를 체크하면 되겠구나! 하고 생각했다.

그 결과는 시간초과... 아마 나와 비슷한 경우의 사람들이 꽤 있을 거라 생각하고 정리해볼까 한다.

 

먼저, 위 아이디어 자체는 틀리지 않다. 맞다고 해도 좋을 것이다.

그런데 위에서 처럼 모든 벽에 대해 bfs를 순회한다? 그렇게 되면 중복 검사를 하는 배열의 수가 아주 많아져 결국 시간초과로 결론이 날 수 밖에 없는 것이다.

그럼 어떻게 해야할까? 간단히, 중복 검사를 최소화하면 된다.

아래는 내가 문제를 풀었던 코드이다.

//2021.10.08
#include<iostream>
#include<vector>
#include<queue>
using namespace std;

class point{
public:
    int x, y;
    point(int X, int Y){
        x = X;
        y = Y;
    }
    point(){
    }
};

int a[1000][1000];
int check[1000][1000];
int n, m;
vector<point> wall;
vector<int> len;
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, 1, -1};

bool isIn(int x, int y){
    if(x < 0 || y < 0 || x >= n || y >= m) return false;
    return true;
}

void bfs(int x, int y, int flag){
    queue<point> q;
    q.push(point(x, y));
    a[x][y] = flag;
    while(!q.empty()){
        point node = q.front(); q.pop();
        for(int i = 0; i < 4; i++){
            int nx = node.x + dx[i];
            int ny = node.y + dy[i];
            if(isIn(nx, ny) && a[nx][ny] == 0){
                q.push(point(nx, ny));
                a[nx][ny] = flag;
                len[flag*(-1)]++;
            }
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    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++){
            a[i][j] = input[j]-'0';
            if(a[i][j] == 1) wall.push_back(point(i, j));
        }
    }
    len.push_back(0);
    int flag = -1;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(a[i][j] == 0){
                len.push_back(1);
                bfs(i, j, flag);
                flag -= 1;
            }
        }
    }
    vector<bool> sumCheck(flag*(-1), false);
    for(point p: wall){
        for(int i = 0; i < 4; i++){
            int nx = p.x + dx[i];
            int ny = p.y + dy[i];
            if(isIn(nx, ny)){
                if(a[nx][ny] < 0 && sumCheck[a[nx][ny]*(-1)] == false) {
                    a[p.x][p.y] += len[a[nx][ny]*(-1)]%10;
                    sumCheck[a[nx][ny]*(-1)] = true;
                }
            }
        }
        sumCheck.assign(flag*(-1), false);
    }
    string ans = "";
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(a[i][j] < 0) ans += '0';
            else ans += '0' + a[i][j]%10;
        }
        ans += '\n';
    }

    cout << ans;
}

각각의 요소에 대해 간단하게 설명하자면,

class point는 bfs의 큐에서 각 점의 좌표를 저장하여 사용하기 위함이다(그냥 pair를 쓰기 귀찮았다..)

flag는 순회 가능한(연결된) 각각의 좌표들에 대해 같은 색으로 칠하기 위한 변수라고 보면 좋을 것 같다.(flag를 음수로 한것은 그저 저장 공간을 조금이라도 아껴보려고... 큰 의미는 없으니 신경 쓰지 않아도 될 것 같다.)

len 벡터는 flag로 인해 같은 값이 된 0값을 가진 각 좌표들의 수(즉, 이동 가능한 좌표들의 수)를 표시한 것이다.

wall 벡터는 각 벽의 좌표를 저장해둔다.

 

알고리즘에 대해 설명하자면,

bfs 함수의 경우는 각 0값을 가진 좌표들이 서로 누구와 연결이 되는지(한번에 순회가 가능한지)를 검사하여 flag 값에 따라 각각을 색칠하고, 같은 flag로 색칠된 좌표들의 수를 len 벡터에 저장해둔다.

이후 sumCheck 벡터 선언부 이후부터는 각각의 벽 좌표에 대해 bfs순회를 하는데, 주변 len 벡터에 따라 순회 가능한 flag들을 검사하여 flag에 해당하는 len 벡터의 값의 총합을 해당 벽 좌표에 넣어준다.

sumCheck는 해당 인덱스(flag)의 len 벡터값을 더해줬는지 검사해주는 배열로 사용하였다.

 

이후 마지막 출력부는 출력 시간의 단축을 위해 문자열로 저장하여 한번에 출력해주었다.

 

설명이 좀 부족할 수도, 생략된 부분이 있을 수도 있다고 생각한다.

혹시 도움이 필요하거나 질문이 있으면 남겨주면 발견하는 대로 대답할 수 있도록 하겠다.

 

긴글 읽어주셔서 감사합니다. 부디 도움이 되는 글이었으면 좋겠습니다.