[BOJ] #2573 빙산

시간 제한	메모리 제한	정답 비율
1 초	256 MB	26.092 %

 

2573번: 빙산

한 덩어리의 빙산이 주어질 때, 이 빙산이 두 덩어리 이상으로 분리되는 최초의 시간(년)을 구하는 프로그램을 작성하시오.

동서남북 네 방향으로 인접한 0의 개수만큼 한 칸에 있는 빙산의 크기는 줄어든다.

BFS queue 사용. = 1년 후 빙산 모습. DFS 덩어리 몇 개인지 확인. 덩어리가 1개 이하라면 위의 과정 반복. while

처음엔 무조건 1덩어리 이므로 BFS 먼저 도는게 맞음.

주의한 점은 먼저 빙산의 크기를 줄여버리면 인접한 빙산에서볼때는 원래 있었던 빙산인데 0으로 인식할 수 있으므로 chk 배열을 활용하여 그 부분은 바닷물이 아니게 인식하도록 함.

• testcase 1
  5 7
  0 0 0 0 0 0 0
  0 0 0 0 0 0 0
  0 0 10 0 0 0 0
  0 0 0 0 0 0 0
  0 0 0 0 0 0 0
  0
• testcase 2
  5 7
  0 0 0 0 0 0 0
  0 3 6 3 6 7 0
  0 3 0 0 0 10 0
  0 0 0 0 0 0 0
  0 0 0 0 0 0 0
  2
• testcase 3
  5 7
  0 0 0 0 0 0 0
  0 9 8 3 8 9 0
  0 9 8 0 8 9 0
  0 9 8 9 8 9 0
  0 0 0 0 0 0 0
  5
• testcase 4
  5 5
  0 0 0 0 0
  0 6 9 6 0
  0 3 3 9 0
  0 6 1 6 0
  0 0 0 0 0
  4
  
  

메모리	시간
2876 KB	72 ms

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
 
int di[] = { 0,0,1,-1 };
int dj[] = { 1,-1,0,0 };
int n, m, cnt = -1, answer;
int arr[301][301];
int chk[301][301];
 
void dfs(int r, int c) {
    chk[r][c] = 1;
    for (int i = 0; i < 4; i++) {
        int nextr = r + di[i];
        int nextc = c + dj[i];
        if (nextr >= 0 && nextr < n && nextc >= 0 && nextc < m) {
            if (arr[nextr][nextc] && !chk[nextr][nextc]) {
                dfs(nextr, nextc);
            }
        }
    }
}
 
void dfs_nextyear(int r, int c) {
    chk[r][c] = 1;
    for (int i = 0; i < 4; i++) {
        int nextr = r + di[i];
        int nextc = c + dj[i];
        if (nextr >= 0 && nextr < n && nextc >= 0 && nextc < m) {
            if (!arr[nextr][nextc] && !chk[nextr][nextc]) {
                if (arr[r][c] > 0) arr[r][c]--;
            }
        }
    }
}
 
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%d", &arr[i][j]);
        }
    }
 
    while (cnt < 2) {
        if (cnt == 0) {
            answer = 0; break;
        }
        cnt = 0;
 
        // 1년 후 변한 모습
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (arr[i][j]) {
                    dfs_nextyear(i, j);
                }
            }
        }
        answer++;
 
        memset(chk, 0, sizeof(chk));
 
        // 덩어리 개수 확인
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (arr[i][j] && !chk[i][j]) {
                    dfs(i, j);
                    cnt++;
                }
            }
        }
        memset(chk, 0, sizeof(chk));
    }
    printf("%d", answer);
    return 0;
}