[BOJ / C++] #2573 빙산

https://www.acmicpc.net/problem/2573

35' ㅋㅋㅋㅋㅋㅋㅋㅋ삼항연산자 문법 내멋대로 제작했다가 헤맴...
반환받을 변수를 꼭 명시해주기 🤣

문제풀이

BFS를 이용한 간단한 시뮬레이션 느낌이다.

0. while문 안에서 시간을 계속 증가시키면서 시뮬레이션을 돌린다.
덩어리를 2개이상 찾으면 while문을 종료한다.
while문 안에서 일어나는 과정은

1.❄️ meltIce()
빙산이 있는 좌표 주변의 바다 개수를 세서 tmpMap에 저장해놓고,
마지막에 map-tmpMap을 해주면 된다.
😇 이 때 맵은 음수가 될 수 없어서 삼항연산자를 써줬는데 문법 틀려서 잘 안돌아감..

map[i][j]=(map[i][j]-tmpMap[i][j]>0)? map[i][j]-tmpMap[i][j]:0;

기억해..

+) 처음에 빙산이 있는 좌표를 모두 큐에 넣고 돌렸는데..딱히 그렇게 안하고
그냥 map을 전부 돌면서 빙산이 있는 지점에서 세주는 게 나을 것 같다.

+) 빙산이 하나도 없으면 0을 출력해야 하므로 이것도 생각해주기.

2. ❄️ 덩어리 개수 세기 BFS
visited배열을 이용해서 MAP을 돌면서 빙산이 있고, 방문한 적 없는 지점을 찾아 시작점으로 하여 흔한 BFS를 실행하면 된다.
개수 세고 나서 2개 이상이면 while문 빠져나오기까지 하면 끝!

코드

#define MAX 300+1
int dr[4]={-1,0,1,0};
int dc[4]={0,1,0,-1};
int N,M;
int map[MAX][MAX];
bool visited[MAX][MAX];
int res=0; //두 덩어리 이상으로 분리되는 최초의 시간
int cntGroup=0;
bool isNotExist=false;
bool found=false;

void meltIce(){
    queue<pair<int,int>> q;
    int tmpMap[MAX][MAX]={0,}; //주변에 있는 0 개수 저장.

    // 빙산이 있는 좌표
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++) {
            if(map[i][j]==0) continue;
            q.push({i,j});
        }
    }

    //빙산이 다 녹아있는 경우
    if(q.empty()){ isNotExist=true; return;}

    while(!q.empty()){
        int r=q.front().first;
        int c=q.front().second;
        q.pop();

        int cnt=0;
        for(int d=0;d<4;d++){
            int nr=r+dr[d];
            int nc=c+dc[d];

            if(nr<0||nr>N-1||nc<0||nc>M-1||map[nr][nc]>0) continue;
            cnt++; //주변에 0인 거 개수 세기
        }

        tmpMap[r][c]=cnt;
    }

    // 빼주기!
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++) {

            //삼항연산자 문법.. 꽤나 웃기게 썼음
            map[i][j]=(map[i][j]-tmpMap[i][j]>0)? map[i][j]-tmpMap[i][j]:0;

            /*
            if(map[i][j]-tmpMap[i][j]>0){
                map[i][j]-=tmpMap[i][j];
            }else{
                map[i][j]=0;
            }
             */
        }
    }
}

void findGroup(int sr, int sc){

    queue<pair<int,int>> q;
    q.push({sr,sc});
    visited[sr][sc]=true;

    while(!q.empty()){
        int r=q.front().first;
        int c=q.front().second;
        q.pop();

        for(int d=0;d<4;d++){
            int nr=r+dr[d];
            int nc=c+dc[d];

            if(nr<0||nr>N-1||nc<0||nc>M-1||map[nr][nc]==0||visited[nr][nc]) continue;
            q.push({nr,nc});
            visited[nr][nc]=true;
        }
    }
}
int main(){
    cin>>N>>M;
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            cin>>map[i][j];
        }
    }

    while(!found){
        res++;
        //1. 녹이기.
        meltIce();

        if(isNotExist){
            cout<<0<<"\n";
            exit(0);
        }

        //2. 덩어리 개수 세기
        memset(visited,false,sizeof(visited));
        cntGroup=0;

        //BFS 시작점
        for(int i=0;i<N;i++){
            for(int j=0;j<M;j++) {
                if(map[i][j]&&!visited[i][j]){
                    //덩어리 하나씩 세기
                    findGroup(i,j);
                    cntGroup++;

                    if(cntGroup>=2) {
                        found=true;
                        break;
                    }
                }
            }
        }
    }
    cout<<res<<"\n";
}