DFS+BFS (BOJ 2573)

문제

빙산

알고리즘

1. BFS로 iceMap 탐색, iceMap 전체를 탐색할 때마다 age를 +1
2. 높이가 0인 좌표는 age, 이외는 age+1로 방문 표시
3. 높이가 0보다 큰 좌표(ice)를 iceberg에 저장
4. 0과 이웃한 좌표를 녹이는 과정에서 0이 된 좌표의 수(melted)를 기록
5. iceberg의 크기와 melted로 빙산의 전체 크기를 계산 (iceberg.size() - melted)
6. DFS로 연결된 빙산의 크기를 추적
7. 4와 5를 비교해 값이 다르면 age를 리턴
8. 모든 얼음이 녹았으면 0을 리턴

코드

#include<bits/stdc++.h>

using namespace std;

int row, col, ice, melted, age = 0;
int visited[301][301] = {0,};
bool connect = true;

vector<vector<int>> iceMap;
queue<pair<int,int>> iceQue;
vector<pair<int,int>> iceberg;
vector<vector<int>> adj = {
    { 1, 0}, {0,  1},
    {-1, 0}, {0, -1}
};


void input(){
    cin >> row >> col;

    for(int i=0; i<row; i++){
        vector<int>  iceRow;

        for(int j=0; j<col; j++){
            int high;
            cin >> high;

            iceRow.push_back(high);
        }
        iceMap .push_back(iceRow);
    }

}

bool rangeCheck(int y, int x){
    return (0 <= y && y < row) && (0 <= x && x < col);
}

void melt(int y, int x){
    if(iceMap[y][x] > 0){
        iceMap[y][x]--;

        if(iceMap[y][x] == 0){
            melted++;
        }
    }
}

pair<int,int> getIBStart(){
    for(int i=0; i<iceberg.size();i++){
        pair<int,int> now = iceberg.at(i);

        if(iceMap.at(now.first).at(now.second) == 0)
            continue;
        else
            return now;
    }

    return pair<int,int>(-1,-1);
}

int DFS(pair<int,int> IBStart, int IBSize){
    int IBY = IBStart.first;
    int IBX = IBStart.second;

    visited[IBY][IBX]--;


    if(iceMap.at(IBY).at(IBX) == 0) return IBSize-1;


    for(int i=0; i<adj.size(); i++){
        int adjY = IBY + adj.at(i).at(0);
        int adjX = IBX + adj.at(i).at(1);

        if(rangeCheck(adjY, adjX)){
            if(visited[adjY][adjX] > age){
                IBSize =  max(IBSize, DFS(pair<int,int>(adjY, adjX), IBSize+1));

            }
        }
    }

    return IBSize;
}

void years(){

    while(1){
        int startY = 0, startX = 0;

        age++;
        visited[startY][startX] = age;

        for(int i=0; i<adj.size(); i++){
            int nextY = startY + adj.at(i).at(0);
            int nextX = startX + adj.at(i).at(1);

            if(rangeCheck(nextY, nextX)){
                int nextIce = iceMap[nextY][nextX];

                if(visited[nextY][nextX] < age){
                    pair<int,int> next(nextY, nextX);

                    iceQue.push(next);
                    visited[nextY][nextX] = age;

                    if(nextIce >0){
                        visited[nextY][nextX]++;
                        iceberg.push_back(next);
                    }
                }
            }
        }

        pair<int,int> now;
        melted = 0;

        while(!iceQue.empty()){


            pair<int, int> now = iceQue.front();

            int nowY  = now.first , nowX = now.second;
            int nowIce = iceMap[nowY][nowX];


            for(int i=0; i<adj.size(); i++){
                int nextY = nowY + adj.at(i).at(0);
                int nextX = nowX + adj.at(i).at(1);

                if(rangeCheck(nextY, nextX)){
                    int nextIce = iceMap[nextY][nextX];

                    if(visited[nextY][nextX] < age){
                        pair<int,int> next(nextY, nextX);
                        iceQue.push(next);

                        visited[nextY][nextX] = age;

                        if(nextIce >0){
                            visited[nextY][nextX]++;
                            iceberg.push_back(next);
                        }
                    }

                    if(nextIce == 0 && visited[nextY][nextX] <= age) melt(nowY, nowX);
                }
            }

            iceQue.pop();
        }



        pair<int, int> IBS = getIBStart();

        if(IBS.first == -1 && IBS.second == -1){
            iceberg.clear();
            return ;
        }

        int ibsize = DFS(IBS,1);
        int wholeIB = iceberg.size() - melted;

        if(wholeIB != ibsize){
            return;
        }

        iceberg.clear();
    }
}


void output(){
    if(iceberg.empty()) cout << 0 << endl;
    else                 cout << age << endl;
}

void run(){
    input();
    years();
    output();
}

int main(){
    run();
    return 0;
}

후기

며칠 전 시도했지만 실패했던 문제
cout으로 디버깅을 하니 시간 낭비도 심했지만
무엇보다 코드가 너무 복잡해진게 아쉽다.
그래도 덕분에 BFS와 DFS에 익숙해진 듯 해서
나름 만족스러웠던 풀이