[C++][백준 2573] 빙산

[문제]

2573번: 빙산 (acmicpc.net)

2573번: 빙산

[문제 풀이]

근처에 0이 있는 수만큼 양수가 줄어들 때(단 0이하로는 안 내려간다) 몇번을 반복해야 1번의 BFS / DFS로 모든 양수를 방문을 못하는지 알아보는 문제이다.

여기서는 BFS를 이용해서 문제를 풀었다.

 

해당 문제를 풀기 위해 크게 2개의 함수를 통해 조건을 나누었다.

1. 양수들을 방문하면서 근처에 있는 0의 수만큼 줄어들게 만드는 함수.

2. BFS를 이용했을때 한번에 모든 양수를 방문하는지 확인을 하는 함수.

 

1번에서 주의사항은 vec값을 줄어들게 만드는 방식으로 문제를 풀면 앞서 줄어들었던 수가 0이 되면서 뒤의 숫자한테 영향을 줄 수가 있다는 것이다.

그렇기에 vec값을 복사한 arr값을 만들어서 근처에 있는 숫자는 arr을 통해서 확인을 하였다.

 

2. BFS를 이용해서 한번에 끝나는지를 확인하는 함수인데 해당 함수는 반대로 보자면 모든 양수값을 체크한 값과 BFS 한번을 돌면서 양수를 체크한 값이 다르다면 BFS를 1번 이상 해야 하는 것으로 확인이 가능하다.

그렇기에 배열을 방문하면서 값이 0이 아닌 숫자 1개만을 들고 시작해서 총 몇번을 중복 방문 없이 방문이 가능한지를 확인해 주면 된다.

[회고]

어렵지 않아 보이지만 막상 풀어보면 생각보다 조건이 많아서 코드가 길어져서 힘들었던 문제였다.

중간에 코드에서

q = qPush(q);
if(q.size() == 0){
    answer = 0;
    break;
}

해당 부분에 answer = 0을 안 넣어줘서 한번 틀렸다. 넣어줘야 하는 이유는 이때 q.size() 가 0이 될때 한번에 모두 0이 된거이니 문제에서 요구하는 다 녹을 때까지 분리되지 않은 경우이기 때문이다.

 

[코드]

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int n,m;    
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};
vector<vector<int> > vec;
vector<vector<int> > arr;
vector<vector<int> > visited;

queue<pair<int, int> > qPush(queue<pair<int, int> > q){
    queue<pair<int,int> > answer;

    for(int i = 0;i<n;i++){
        for(int j = 0;j<m;j++){
            if(vec[i][j] != 0){
                answer.push(make_pair(i,j));
            }
        }
    }
    return answer;
}

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

void bfs(queue<pair<int, int> > q){
    
    arr = vec;

    while(q.size() > 0){
        int curX = q.front().first;
        int curY = q.front().second;
        q.pop();
        for(int i = 0;i<4;i++){
            int nextX = curX + dx[i];
            int nextY = curY + dy[i];
            if(isRange(nextX,nextY) == true && arr[nextX][nextY] == 0){
                if(vec[curX][curY] > 0){
                    vec[curX][curY] -= 1;
                }
            }
        }
    }

    return;
}

void visitedClaer(){
    for(int i = 0;i<n;i++){
        for(int j = 0;j<m;j++){
            visited[i][j] = 0;
        }
    }
    return;
}

bool isDivide(){
    visitedClaer();

    bool answer = false;
    queue<pair<int,int> > q;
    bool flag = false;
    int idx = 0;
    for(int i = 0;i<n;i++){
        for(int j = 0;j<m;j++){
            if(vec[i][j] != 0){
                q.push(make_pair(i,j));
                visited[i][j] = 1;
                idx = 1;
                flag = true;
            }
            if(flag == true)
                break;
        }
        if(flag == true)
            break;
    }

    while(q.size() > 0){
        int curX = q.front().first;
        int curY = q.front().second;
        q.pop();
        for(int i = 0;i<4;i++){
            int nextX = curX + dx[i];
            int nextY = curY + dy[i];
            if(isRange(nextX,nextY) == true && vec[nextX][nextY] != 0 && visited[nextX][nextY] == 0){
                visited[nextX][nextY] = 1;
                q.push(make_pair(nextX,nextY));
                idx++;
            }
        }
    }

    if(idx != qPush(q).size()){
        //크기가 다르다면 분리가 완료된거임.
        answer = true;
    }

    return answer;
}

int main(){
    cin>>n>>m;
    vec.resize(n,vector<int>(m,0));
    visited.resize(n,vector<int>(m,0));

    queue<pair<int, int> > q;
    for(int i = 0;i<n;i++){
        for(int j = 0;j<m;j++){
            cin>>vec[i][j];
        }
    }

    int answer = 0;

    while(true){
        q = qPush(q);
        if(q.size() == 0){
            answer = 0;
            break;
        }
        bfs(q);
        answer++;
        if(isDivide() == true){
            break;
        }
    }

    cout<<answer<<endl;
    return 0;
}