[백준] 2573 빙산

빙산의 덩어리 개수를 파악하기 위해서 자신 있게 dfs를 이용하여 문제를 풀었지만

결과는 시간초과 ㅜㅜ (dfs 안써..)

 

□ 망한 코드.. ㅎ (잘못 나올 수 도 있어요!)

vector<vector<int>> input2573(301,vector<int>(301,0));
vector<vector<int>> modSea2573(301,vector<int>(301,0));
vector<vector<bool>> check2573(301,vector<bool>(301,false));
int N2573, M2573;

bool dfs2573(int x, int y, bool check){

    if(x<1 || y<1 || x>N2573 || y > M2573)
        return false;

    if(check){
        if(modSea2573[x][y] == 0 && input2573[x][y] != 0 && !check2573[x][y]){
            int countSea = 0;
            if(input2573[x+1][y] == 0)
                countSea++;
            if(input2573[x-1][y] == 0)
                countSea++;
            if(input2573[x][y-1] == 0)
                countSea++;
            if(input2573[x][y+1] == 0)
                countSea++;

            check2573[x][y] = true;
            modSea2573[x][y] = countSea;

            dfs2573(x+1, y,check);
            dfs2573(x-1, y, check);
            dfs2573(x, y-1, check);
            dfs2573(x, y+1, check);

            return true;
        }
    }
    else{
        if(modSea2573[x][y] != 0 && input2573[x][y] > 0 && !check2573[x][y]){
            if(input2573[x][y] >= modSea2573[x][y])
                input2573[x][y] -= modSea2573[x][y];
            else
                input2573[x][y] = 0;

            check2573[x][y] = true;
            dfs2573(x+1, y, check);
            dfs2573(x-1, y, check);
            dfs2573(x, y-1, check);
            dfs2573(x, y+1, check);
            return true;
        }
    }

    return false;
}

void snow2573(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin>>N2573>>M2573;

    for(int i=1;i<=N2573;++i){
        for(int j=1; j<=M2573; ++j){
            cin>> input2573[i][j];
        }
    }

    int time = 0;
    while(1){
        int count = 0;

        for(int i=1;i<=N2573;++i)
            for(int j=1; j<=M2573; ++j)
                if(dfs2573(i, j, true))
                    count++;

        if(count >= 2){
            cout<<time<<"\n";
            break;
        }

        fill(check2573.begin(), check2573.end(), vector<bool>(301,false));

        for(int i=1;i<=N2573;++i){
            for(int j=1; j<=M2573; ++j){
                dfs2573(i, j, false);
            }
        }
        time ++;

        fill(check2573.begin(), check2573.end(), vector<bool>(301,false));
        fill(modSea2573.begin(), modSea2573.end(), vector<int>(301,0));
    }
}

 

알고리즘 센세의 조언과 도움으로 bfs코드로 재 구현!

#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> input2573(301,vector<int>(301,0));
vector<vector<int>> modSea2573(301,vector<int>(301,0));
vector<vector<bool>> check2573(301,vector<bool>(301,false));
queue<pair<int, int>> q2573;
int N2573, M2573;

void checkBfs2573(){
    
    int dx[] = {0,0,1,-1};
    int dy[] = {1,-1,0,0};
    
    while(!q2573.empty()){
        int x = q2573.front().first;
        int y = q2573.front().second;
        q2573.pop();
        
        for(int i=0; i<4; ++i){
            int mx = dx[i] + x;
            int my = dy[i] + y;
            
            if(mx<1 || my<1 || mx>N2573 || my>M2573)
                continue;
            
            if(input2573[mx][my] != 0 and !check2573[mx][my]){
                check2573[mx][my] = true;
                q2573.push({mx,my});
            }
            if(input2573[mx][my] == 0)
                modSea2573[x][y] += 1;
        }
    }
    
}

void snow2573(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin>>N2573>>M2573;
    
    int ice = 0;
    for(int i=1;i<=N2573;++i){
        for(int j=1; j<=M2573; ++j){
            cin>> input2573[i][j];
            if(input2573[i][j] != 0)
                ice++;
        }
    }
    
    int time = 0;
    while(ice){
        
        int count = 0;
        //MARK:  덩어리 개수 확인
        for(int i=1; i<=N2573; ++i){
            for(int j=1; j<=M2573; ++j){
                if(input2573[i][j] != 0 && !check2573[i][j]){
                    count++;
                    check2573[i][j] = true;
                    q2573.push({i,j});
                    checkBfs2573();
                }
            }
        }
        
        if(count >= 2){
            cout<<time<<"\n";
            return;
        }
        
        fill(check2573.begin(), check2573.end(), vector<bool>(301,false));
        
        time++;
        for(int i=1; i<=N2573; ++i){
            for(int j=1; j<=M2573; ++j){
                if(input2573[i][j] != 0 and !check2573[i][j]){
                    check2573[i][j] = true;
                    input2573[i][j] = max(0, input2573[i][j] - modSea2573[i][j]);
                    
                    if(input2573[i][j] == 0){
                        ice--;
                    }
                }
            }
        }
        
        fill(check2573.begin(), check2573.end(), vector<bool>(301,false));
        fill(modSea2573.begin(), modSea2573.end(), vector<int>(301,0));
    }
    
    cout<<"0\n";
}

알고리즘 문제를 풀면 풀 수록 더 어렵게 느껴진다 ㅜ