[백준][C++] 2573번: 빙산 <179>

직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다.

 

생각의 흐름

이 문제는 학습할 부분이 많은 문제이다.

 

1) 정점을 각각 따로 처리하면 안된다.

바로 바닷물과 접해있는 칸 수 만큼 빙산을 녹이는 과정에서, 정점 하나하나 마다 진행하면 안된다는 점 이다.

다음 그림을 살펴보자.

위의 주어진 맵에서 빨강색으로 표시된 정점에 대해서 살펴보자.

빙산의 높이가 4이고, 주변에 바닷물(0)이 2곳 인접해 있기 때문에 1년이 지나면 빨간 곳의 높이는 2가 된다.

파랑색으로 표시된 정점은 1년이 지난다면 인근 바다가 1곳이라 2가 된다.

 

하지만, 여기서 저 빨강색과 파랑색 사이(1,1지점) 에 있는 '2' 인 정점을 보자.

 

저 정점은 1년후에 0이 될 것이다. 바다가 2곳 인접해 있기 때문이다.

 

만약에, 여기서 정점 마다 값을 계속 각각 바꾼다고 생각해보자.

위에서 말한 '2'인 정점은 0이 될 것이고, 그 이후에 빨강 정점은 주변에 0이 3개가 있으므로 1년후에 값이 1로 바뀌게 된다.

2로 바뀌어야 하는데 1로 바뀐것 이다!

 

따라서, 1년 후의 녹을 양을 저장한 value라는 배열을 따로 만들어 준다.

 

2) 예외 처리의 중요성

- 이 문제에서는 빙산이 다 녹을때까지 1덩어리가 될수도 있음을 주의해야 한다.

- 시작부터 빙산이 전부 녹았을 경우도 생각해주면 좋다.

 

나의 코드

#include <bits/stdc++.h>
using namespace std;
#define MAX 301

int N, M;
int MAP[MAX][MAX];
bool visited[MAX][MAX];
int value[MAX][MAX];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, -1, 0, 1};
int year = 0;

void BFS(int x, int y){
    queue<pair<int, int> > Q;
    Q.push({x, y});
    visited[x][y] = true;

    while(!Q.empty()){
        int nowX = Q.front().first;
        int nowY = Q.front().second;
        Q.pop();

        for(int i = 0; i < 4; i++){
            int nx = nowX + dx[i];
            int ny = nowY + dy[i];
            if(nx < 0 || ny < 0 || nx >= N || ny >= M) continue;

            if(!visited[nx][ny] && MAP[nx][ny] != 0){
                visited[nx][ny] = true;
                Q.push({nx, ny});
            }
        }
    }
}

bool mapChecker(){
    int cnt = 0;
    memset(visited, false, sizeof(visited));
    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            if(MAP[i][j] != 0 && !visited[i][j]){
                BFS(i, j);
                cnt++;
                if(cnt >= 2){
                    return false;
                }
            }
        }
    }
    return true;
}

void go(){
    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            if(MAP[i][j] != 0){
                int cnt = 0;
                for(int k = 0; k < 4; k++){
                    int nx = i + dx[k];
                    int ny = j + dy[k];
                    if(nx < 0 || ny < 0 || nx >= N || ny >= M) continue;

                    if(MAP[nx][ny] == 0){
                        cnt++;
                    }
                }
                value[i][j] = cnt;
            }
        }
    }

    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            MAP[i][j] -= value[i][j];
            if(MAP[i][j] < 0){
                MAP[i][j] = 0;
            }
        }
    }
}

bool isMelted() {
    for (int r = 0; r < N; r++)
        for (int c = 0; c < M; c++)
            if (MAP[r][c] != 0)
                return false;

    return true;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> M;
    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            cin >> MAP[i][j];
        }
    }

    if(isMelted()){
        cout << 0 << "\n";
        return 0;
    }

    while(mapChecker()) {
        go();
        year++;
        if(isMelted()){
            cout << 0;
            return 0;
        }
    }


    cout << year;

    return 0;
}