[백준][2573] 빙산

이 포스트는 백준 사이트의 빙산 문제 풀이입니다.

문제

해결 과정

이 문제는 BFS와 시뮬레이션으로 문제를 해결할 수 있습니다.

여기서 가장 중요한 것은 BFS를 사용해서 무엇을 탐색할지 입니다.
입력받은 모든 칸을 순회하면서 주위에 얼음을 확인할 경우, 시간이 오래걸리기 때문에

얼음 위치만 저장하는 큐를 저장하고
큐에서 하나씩 꺼내며 얼음 주위에 물이 있는지 확인하고 4방향 모두 얼음일 때만
새로운 얼음 큐에 넣는 것을 반복하여 얼음의 녹는 시간을 구하였습니다.

마지막으로 얼음을 녹였다면
현재 상태에서 방문을 기록하는 2차원 배열과 BFS를 사용해서 얼음이 2개로 나뉘는지 확인하였습니다.

코드 구현

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

using namespace std;

struct POINT{
    int row, col, hei;
};
int dir_row[4]{-1, 1, 0, 0};
int dir_col[4]{0, 0, -1, 1};

int N, M;
vector<vector<int>> board;
queue<POINT> q_ice;

void input();
void check_ice_area(int row, int col, vector<vector<bool>>& visited);
int count_ice_area();
void melt_ice();


int main() {
    input();

    int answer = 0;
    while(true) {
        int area_cnt = count_ice_area();
        
        if(area_cnt == 0) {
            answer = 0;
            break;
        } else if(area_cnt >= 2) {
            break;
        } else {
            melt_ice();
            answer += 1;   
        }
    }

    cout << answer;
    return 0;
}


void input() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> N >> M;
    board.assign(N, vector<int>(M, 0));

    for(int row = 0; row < N; ++row) {
        for(int col = 0; col < M; ++col) {
            cin >> board[row][col];
            if(0 != board[row][col]) {
                q_ice.push(POINT{row, col, board[row][col]});
            }
        }
    }
}

int count_ice_area() {
    int answer = 0;
    vector<vector<bool>> visited(N, vector<bool>(M, false));
    for(int row = 0; row < N; ++row) {
        for(int col = 0; col < M; ++col) {
            if(board[row][col] && false == visited[row][col]) {
                check_ice_area(row, col, visited);
                answer += 1;
            }
        }
    }
    return answer;
}

void check_ice_area(int row, int col, vector<vector<bool>>& visited) {
    queue<POINT> q;
    q.push(POINT{row, col, 0});

    visited[row][col] = true;
    while(false == q.empty()) {
        auto curr = q.front();
        q.pop();

        for(int dir = 0; dir < 4; ++dir) {
            int new_row = curr.row + dir_row[dir];
            int new_col = curr.col + dir_col[dir];

            if(new_row < 0 || new_row >= N || new_col < 0 || new_col >= M)
                continue;
            if(0 == board[new_row][new_col])
                continue;
            if(visited[new_row][new_col])
                continue;
            visited[new_row][new_col] = true;
            q.push(POINT{new_row, new_col, 0});
        }
    }
}

void melt_ice() {
    queue<POINT> next_year_ice;

    auto next_board = board;
    while(false == q_ice.empty()) {
        auto curr = q_ice.front();
        q_ice.pop();

        int near_ocean_cnt = 0;
        for(int dir = 0; dir < 4; ++dir) {
            int new_row = curr.row + dir_row[dir];
            int new_col = curr.col + dir_col[dir];

            if(new_row < 0 || new_row >= N || new_col < 0 || new_col >= M)
                continue;
            if(0 == board[new_row][new_col]) {
                near_ocean_cnt += 1;
            }
        }

        if(near_ocean_cnt > 0) {
            next_board[curr.row][curr.col] = board[curr.row][curr.col] - near_ocean_cnt >= 0 
                ? board[curr.row][curr.col] - near_ocean_cnt : 0;

            if(next_board[curr.row][curr.col] > 0) {
                next_year_ice.push(POINT{curr.row, curr.col, next_board[curr.row][curr.col]});
            }
        } else {
            next_year_ice.push(POINT{curr.row, curr.col, board[curr.row][curr.col]});
        }
    }

    board = next_board;
    q_ice = next_year_ice;
}

실행 결과