[백준/BOJ 알고리즘] 2573 빙산 C++

> www.acmicpc.net/problem/2573

2573번: 빙산

오랜만에 알고리즘 풀다가 마음대로 안되서 화가 났던 문제이다..... 그래도 맞아서 기분 좋다.

 

기본적인 그래프 탐색을 통해 해결할 수 있는 문제이다.

난 DFS를 통해 구현했다.

문제의 핵심 

• 빙산 높이가 담긴 배열의 가장자리는 모두 0 이므로, 탐색대상에서 제외해야한다.
• 각 빙산의 높이가 1년마다 얼만큼 녹을 지 상하좌우의 빙산을 탐색하여 모든 빙산의 녹는 정도를 구한 후에 빙산을 녹여야한다.
• 빙산 덩어리의 개수를 정확히 구하지 않아도 된다. 한개보다 많거나 녹을 빙산이 없다면 더 이상 탐색하지 않아도 된다.
• 모든 빙산이 녹기 전까지 두 덩어리가 되지 않는다면 0을 출력해야한다. 

구현  

• 반복문을 통해 1년 단위로 빙산 덩어리 개수를 파악하고, 녹인다.
• 덩어리개수구하기() 
  • 높이가 0보다 크며 방문하지 않은 빙산을 골라 dfs() 를 호출한다.
  • 덩어리개수를 1 증가 시킨다.
  • 덩어리개수가 1 이상이라면 다시 dfs를 호출하지 않고, 덩어리개수를 반환하며 함수를 종료시킨다.
• 빙산녹이기()
  • 가장자리를 제외한 빙산_1 의 상하좌우를 탐색한다.
  • 상하좌우에 위치한 빙산 중 높이가 0 이하인 빙산의 개수가 빙산_1의 녹는 정도가 된다.
  • 각 빙산의 녹는 정도를 모두 구한 후 실제 빙산의 높이에서 녹는 정도를 빼준다.
• 0을 출력하게 되는 조건
  
  • 녹일 빙산이 없다. (= 높이가 1이상인 빙산이 없다)  즉, 높이가 양수 값을 갖는 빙산이 없다면 0을 출력하면 된다.

 

> 코드가 궁금하다면, 포스트 하단의 더보기를 눌러주세요

 

 

* 코드에 대한 피드백은 언제나 환영합니다. *

 

#include <stdio.h>
#include <utility>
#include <cstring>
using namespace std;

int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}};

int ice[301][301]={};
int toMelt[301][301];
int visited[301][301];

bool isAllZero(int n, int m) {
    for(int i=2;i<n;i++) for(int j=2;j<m;j++) if( ice[i][j] > 0 ) return false;
    return true;
}

void dfs(int x, int y){
    int to_x, to_y;
    // 방문한 얼음을 방문체크 해줌.
    visited[x][y] = 1;
    for(int i=0;i<4;i++){
        // 상하좌우로 이동 가능한 얼음의 좌표를 to_x, to_y 에 할당 
        to_x = x+dir[i][0]; to_y = y+dir[i][1];
        // 방문하지 않았고, 빙산이 있는 얼음에 한해서만 탐색.
        if(ice[to_x][to_y]>0 && !visited[to_x][to_y]) dfs(to_x,to_y);
    }
}

int piece(int n, int m){
    // bfs를 통해 조각 개수를 파악.
    int cnt = 0;
    for(int i=2;i<n;i++){
        for(int j=2;j<m;j++){
            // 방문하지 않았고, 빙산이 있는 얼음에 한해서만 탐색.
            if(!visited[i][j] && ice[i][j] > 0){
                if(cnt > 0) return 2;
                dfs(i,j);
                cnt++;
            }
        }
    }
    return cnt;
}

void melt(int n, int m){
    int to_x, to_y;
    for(int i=2;i<n;i++){
        for(int j=2;j<m;j++){
            for(int k=0;k<4;k++){
                to_x = i+dir[k][0]; to_y = j+dir[k][1];
                if(ice[to_x][to_y] <= 0 ) toMelt[i][j]++;
            }
        }
    }

    for(int i=2;i<n;i++) for(int j=2;j<m;j++) if(ice[i][j] > 0) ice[i][j] -= toMelt[i][j];    
}

int main() {
    int n,m, year = 0, num_piece, allZeroFlag = 0;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&ice[i][j]);

    while(1) {
        memset(visited, 0, sizeof(visited));
        memset(toMelt, 0, sizeof(toMelt));
        
        num_piece = piece(n,m);
        
        // 빙산 조각의 개수 판별.
        if(num_piece > 1) break;
        melt(n,m);

        if(isAllZero(n,m)) {
            allZeroFlag = 1;
            break;
        }
        year++;
    }
    if(allZeroFlag) printf("0\n");
    else {
        printf("%d\n",year);
    }
    return 0;
}