[백준] 빙산

백준 그래프 추천문제인 빙산 문제를 풀어봤다. 문제 자체는 꽤 쉬운데 쉽게 실수를 할 수 있을법한 문제다. 그래도 솔직히 이런 시뮬레이션이 섞인 BFS 문제를 백준에서 많이 풀어봐서 그런지 문제를 읽자마자 어떻게 풀어야할지 감이 왔고. 코드를 다 만든 후 에도 다시 읽어보면서 실수가 나올 부분에서 모두 에러체킹을 머리속에서 해주었다.

확실히 이 전에 있었던 힘든 경험들이 이런 시뮬레이션 타입 문제에 더 강점을 부여해준거같아서 기분이 좋다.

실수를 할만했던 코드 중에는 뭉친 빙산을 확인 해줄때랑 빙산을 녹이는 과정인데. 이 둘의 순서를 잘 생각하면서 해줘야지 문제없이 테스트가 통과했을거다. 예전에 아기 상어 문제들을 풀때가 좀 생각이 났고 같은 실수는 하지않아서 다행이다.

#include <iostream> 
#include <bits/stdc++.h> 
#define endl "\n"
#define MAX 100010
using namespace std;

int N,M; 
int matrix[301][301];
int ocean[301][301]; 
bool visited[301][301]; 
vector<pair<int,int>> dir = {{0,1},{0,-1},{1,0},{-1,0}}; 

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

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

    while(!q.empty()){
        int size = q.size();
        for(int i = 0; i < size; i++){
            pair<int,int> first = q.front();
            q.pop(); 

            int xx = first.first, yy = first.second;

            for(pair<int,int>& p : dir){
                int nX = xx + p.first;
                int nY = yy + p.second; 

                if(nX < 0 || nY < 0 || nX >= N || nY >= M || visited[nX][nY] || matrix[nX][nY] <= 0) continue; 

                q.push({nX,nY}); 
                visited[nX][nY] = true; 
            }
        }
    }
}

void melt(int i, int j){
    int oceanCnt = 0; 
    for(pair<int,int>& p : dir){
        int nX = i + p.first;
        int nY = j + p.second;

        if(nX < 0 || nY < 0 || nX >= N || nY >= M || matrix[nX][nY] != 0) continue; 

        if(matrix[nX][nY] == 0) oceanCnt++; 
    }
    ocean[i][j] = oceanCnt; 
}

void Solution(){
    int year = 0, cnt = 0; 
    bool exist = false; 
    while(1){
        memset(visited,false,sizeof(visited)); 
        memset(ocean,0,sizeof(ocean)); 
        for(int i = 0; i < N; i++){
            for(int j = 0; j < M; j++){
                if(matrix[i][j] > 0){
                    exist = true; 
                    if(!visited[i][j]){
                        cnt++; 
                        bfs(i,j); 
                    }
                    melt(i,j); 
                }
            }
        }

        for(int i = 0; i < N; i++){
            for(int j = 0; j < M; j++){
                if(ocean[i][j] > matrix[i][j]) matrix[i][j]  = 0;
                else matrix[i][j] -= ocean[i][j]; 
            }
        }


        if(cnt >= 2){
            cout << year;
            return; 
        }


        if(!exist) break; 
        exist = false; 
        cnt = 0; 
        year++; 
    }
    cout << 0; 

}


void Solve(){
    Input();
    Solution(); 
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen("input.txt", "r", stdin);
    Solve();
    return 0;

}

배운점:
1. visited 배열 활용
2. BFS 의 활용