[백준] 2573번: 빙산 (C++)

 

이번에도 BFS를 활용한 문제

실생활에서 BFS를 많이 사용하는 것일까

BFS가 많이 쓰이는 것 같다

 

빙산 문제는 다음 상태의 배열까지 고려해야 하므로

두 개의 배열을 사용한다 

 

이후 접한 면의 수를 탐색한 후 

그만큼 빼고 다음 상태에 덮어쓰기한다

 

처음보는 함수를 많이 사용했기 때문에 

조금 더 익숙해져야 할 것 같다

 

// baekjoon 2573

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;

// codes for fast I/O
void init(){
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(false);
}


int arr[301][301];
int next_arr[301][301];
bool visited[301][301];

int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
int N, M;

queue<pair<int,int>> q;

int year = 0;

// BFS
void bfs(int a, int b){
    q.push(make_pair(a, b));
    visited[a][b] = true;
    
    while (q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if((nx >= 0 && nx < N) && (ny >= 0 && ny < M) && !visited[nx][ny] && !arr[nx][ny]){
                visited[nx][ny] = true;
                q.push(make_pair(nx, ny));
            }
        }
        
    }
}

int melt(int x, int y){
    int cnt = 0;
    for(int i = 0; i < 4; i++){
        int nx = x + dx[i];
        int ny = y + dy[i];
        
        if(arr[nx][ny] == 0){
            cnt++;
        }
    }
    
    return cnt;
}

// 배열, 방문여부, 큐 초기화
/*
void reset(){
}
*/

int main(){
    init();
    
    cin >> N >> M;
    
    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            cin >> arr[i][j];
        }
    }
    
    while (true) {
        int count = 0;
        memset(visited, false, sizeof(visited));
        memset(next_arr, false, sizeof(next_arr));
        
        for(int i = 0; i < N; i++){
            for(int j = 0; j < M; j++){
                if(arr[i][j] != 0 && !visited[i][j]){
                    count++;
                    bfs(i, j);
                }
            }
        }
        
        if(count >= 2){
            cout << year;
            break;
        }
        if(count == 0){
            cout << 0;
            break;
        }
        
        for(int i = 0; i < N; i++){
            for(int j = 0; j < M; j++){
                if(arr[i][j] != 0){
                    next_arr[i][j] = arr[i][j] - melt(i, j);
                    
                    if(next_arr[i][j] < 0){
                        next_arr[i][j] = 0;
                    }
                }
            }
        }
        
        for(int i = 0; i < N; i++){
            for(int j = 0; j < M; j++){
                arr[i][j] = next_arr[i][j];
            }
        }
        year++;
    }
}