[백준 2573] 빙산

쉬운문젠데 생각보다 걸렸다..

저지른 실수가 너무 많았다..

dfs를 할때 시작 visited 처리, 카운터 증가, 음수 처리 등 평소에 잘 안하는 실수가 잦았다..

문제 자체는 되게 평이하다.

 

첫줄 마지막줄이 항상 0이라는 조건이 있어서  범위끝처리가 필요없어서 좋았다.

문제풀이

 

첫줄 마지막줄이 항상 0이라는 조건이 있어서  범위끝처리가 필요없어서 좋았다.

 

높이가 0보다큰빙산을 벡터에 저장하고 감소 연산을 한뒤에 따로 맵에서 한꺼번에 빼주었다. 이렇게하면 접근도 빠르고 녹을 때 먼저 0이되어 데이터의 오류가 나는 일이 없다. 

 

그리고 빙산의 분리는 빙산전체 카운트와 시작점부터 dfs를하여 갯수 비교를 통해 진행하였다.

 

소스코드

#include <iostream>
#include <queue>
#include <algorithm>
 
using namespace std;
int row_size;
int col_size;
int Map[301][301];
bool visited[301][301];
 
 
typedef struct Ice{
    int height;
    int row;
    int col;
    Ice(int h,int r,int c){
        height =h;
        row =r;
        col =c;
    }
}Ice ;
 
vector<Ice> ices;
int dir_row[4] = {-1,0,1,0};
int dir_col[4] = {0,1,0,-1};
int connected_cnt=0;
bool cmp(Ice &a, Ice &b){
    return a.height>b.height;
}
 
int getReducedHeight(Ice ice){
    int cnt=0;
    for(int i=0;i<4;i++){
        int next_row = ice.row+dir_row[i];
        int next_col = ice.col+dir_col[i];
        if(Map[next_row][next_col]<=0){
            cnt++;
        }
    }
    return cnt;
}
 
void meltIces(){
    for(int i=0;i<ices.size();i++){
        int reduced_height = getReducedHeight(ices[i]);
        ices[i].height -=reduced_height;
    }
    for(int i=0;i<ices.size();i++){
        Map[ices[i].row][ices[i].col] =ices[i].height<0?0:ices[i].height;
    }
}
 
void initVisited(){
    for(int i=0;i<row_size;i++){
        for(int j=0;j<col_size;j++){
            visited[i][j] = false;
        }
    }
}
void dfs(int row, int col){
    for(int i=0;i<4;i++){
        int next_row = row + dir_row[i];
        int next_col = col + dir_col[i];
        if(Map[next_row][next_col]>0 && visited[next_row][next_col]==false){
            connected_cnt++;
            visited[next_row][next_col]=true;
            dfs(next_row,next_col);
        }
    }
}
 
int main() {
    cin>>row_size>>col_size;
    for(int i=0;i<row_size;i++){
        for(int j=0;j<col_size;j++){
            cin>>Map[i][j];
            if(Map[i][j] !=0){
                ices.push_back(Ice(Map[i][j],i,j));
            }
        }
    }
    int year=0;
    while(1){
        year++;
        meltIces();
//        cout<<year<<"년"<<endl;
//        for(int i=0;i<row_size;i++){
//            for(int j=0;j<col_size;j++){
//                cout<<Map[i][j]<<" ";
//            }
//            cout<<endl;
//        }
        sort(ices.begin(),ices.end(),cmp);
        while(!ices.empty()&&ices[ices.size()-1].height<=0){
            ices.pop_back();
        }
        if(ices.empty()){
            cout<<"0"<<endl;
            return 0;
        }
        connected_cnt=1;
        initVisited();
        visited[ices[0].row][ices[0].col]=true;
        dfs(ices[0].row,ices[0].col);
        if(connected_cnt<ices.size()){
//            cout<<connected_cnt<<","<<ices.size()<<endl;
            cout<<year<<endl;
            return 0;
        }
    }
    
    
    
    return 0;
}
 

 

문제 링크 : https://www.acmicpc.net/problem/2573

2573번: 빙산