[BOJ-2573] 빙산

[문제요약]

R*C 크기의 빙산 정보가 주어진다. 0 인 경우 바다를 뜻하며, [1, 10] 사이 값은 빙산의 높이를 뜻한다.

1. 빙산은 처음에 한덩어리로 주어진다.
2. 빙산 주변에 바다가 있다면, 1년 후 빙산의 높이는 4방향 (상하좌우) 에 바다가 있는 양만큼 높이가 줄어든다.
3. 빙산이 한덩어리에서 2덩어리 이상으로 갈라질때 몇 년 후인지 출력한다. 
4. 빙산이 한덩어리에서 쪼개지지 않고, 빙산이 사라지는 경우 '0' 을 출력한다.

[입력]

빙산의 크기 R, C 

빙산의 정보가 주어진다.

[출력]

빙산이 2덩어리 이상으로 쪼개지는 년 수를 구한다. 만약 없다면 0을 출력한다.

[접근방법]

BFS를 이용한다. 

imap[][] : 빙산정보를 저장한다.

check[][] : 현재 빙산을 체크한다.

입력으로 빙산정보를 받은 후, 

빙산이 존재하는 경우, BFS를 수행하여 check[r][c] 위치에 체크를 한다.

이후 빙산을 체크한 정보로  빙산이 없는(==바다)인 경우 주변 4방향(상하좌우) 에 빙산이 존재하는 경우 높이를 -1 한다.

처음 시간을 240ms 를 받아 줄일 수 있는 방법을 생각해보았다. 

이를 줄이기 위해 빙산이 있는 각 위치를 벡터 배열로 받아, 빙산이 위치한 지점만으로 수행시켰다. 

그리하여 72ms 로 연산시간을 줄일 수 있었다.

[C++11 source code BFS]

#include<cstdio>
#include<queue>
#include<memory.h>
#define din1(a) scanf("%d", &a);
using namespace std;
 
const int M = 333;
const int dr[] = { 0,0,1,-1 };
const int dc[] = { 1,-1, 0,0 };
int ROW, COL;
int im[M][M];
bool chk[M][M];
int year;
 
struct pos {
    int R, C;
    pos(int ir, int ic) : R(ir), C(ic) {}
};
 
void bfs(int RO, int CO) {
    queue<pos> Q;
    Q.push(pos(RO, CO));
    chk[RO][CO] = true;
    
    while (!Q.empty()) {
        int hr = Q.front().R;
        int hc = Q.front().C;
        Q.pop();
        
        for (int i = 0; i < 4; i++) {
            int tr = hr + dr[i];
            int tc = hc + dc[i];
            if (tr < 0 || ROW <= tr || tc < 0 || COL < tc) continue;
            if (!chk[tr][tc] && (im[tr][tc] > 0)) {
                chk[tr][tc] = true;
                Q.push(pos(tr, tc));
            }
        }
    }    
}
 
int main() {
    din1(ROW); din1(COL);
    
    for (int r = 0; r < ROW; r++) {
        for (int c = 0; c < COL; c++) {
            din1(im[r][c]);
        }
    } // input
 
    bool is_end = false;
    while (1) {
        int ans = 0;
        for (int r = 0; r < ROW; r++) {
            for (int c = 0; c < COL; c++) {
                if (im[r][c] > 0) {
                    if (chk[r][c]) continue;
                    ans++;
                    bfs(r, c);
                }
            }
        }
 
        for (int r = 0; r < ROW; r++) {
            for (int c = 0; c < COL; c++) {
                if (!chk[r][c]) {
                    for (int i = 0; i < 4; i++) {
                        int tr = r + dr[i];
                        int tc = c + dc[i];
                        if (tr < 0 || ROW <= tr || tc < 0 || COL <= tc) continue;
                        if (im[tr][tc] > 0) im[tr][tc]--;
                    }
                }
            }
        }
        
        if (ans == 0) puts("0"), is_end = true;
        else if (ans > 1) printf("%d\n", year), is_end = true;
        if (is_end) break;
        year++;
        memset(chk, 0, sizeof(chk));
    }
 
    return 0;
}

#include<cstdio>
#include<queue>
#include<memory.h>
#include<vector>
#define din1(a) scanf("%d", &a);
using namespace std;
 
const int M = 333;
const int dr[] = { 0,0,1,-1 };
const int dc[] = { 1,-1, 0,0 };
int ROW, COL;
int im[M][M];
bool chk[M][M];
int year;
 
 
struct pos {
    int R, C;
    pos(int ir, int ic) : R(ir), C(ic) {}
};
 
void bfs(int RO, int CO) {
    queue<pos> Q;
    Q.push(pos(RO, CO));
    chk[RO][CO] = true;
    
    while (!Q.empty()) {
        int hr = Q.front().R;
        int hc = Q.front().C;
        Q.pop();
        
        for (int i = 0; i < 4; i++) {
            int tr = hr + dr[i];
            int tc = hc + dc[i];
            if (tr < 0 || ROW <= tr || tc < 0 || COL < tc) continue;
            if (!chk[tr][tc] && (im[tr][tc] > 0)) {
                chk[tr][tc] = true;
                Q.push(pos(tr, tc));
            }
        }
    }    
}
 
int main() {
    din1(ROW); din1(COL);
    vector<pos> v;
    for (int r = 0; r < ROW; r++) {
        for (int c = 0; c < COL; c++) {
            din1(im[r][c]);
            if (im[r][c]) v.push_back(pos(r, c));
        }
    } // input
 
    bool is_end = false;
    while (1) {
        int ans = 0;
        /*
        for (int r = 0; r < ROW; r++) {
            for (int c = 0; c < COL; c++) {
                if (im[r][c] > 0) {
                    if (chk[r][c]) continue;
                    ans++;
                    bfs(r, c);
                }
            }
        }
        */
        for (int i = 0; i < v.size(); i++) {
            int r = v[i].R;
            int c = v[i].C;
            if (chk[r][c] == 0) {
                if (im[r][c] < 1) continue;
                ans++;
                bfs(r, c);
            }
        }
 
        /*
        for (int r = 0; r < ROW; r++) {
            for (int c = 0; c < COL; c++) {
                if (!chk[r][c]) {
                    for (int i = 0; i < 4; i++) {
                        int tr = r + dr[i];
                        int tc = c + dc[i];
                        if (tr < 0 || ROW <= tr || tc < 0 || COL <= tc) continue;
                        if (im[tr][tc] > 0) im[tr][tc]--;
                    }
                }
            }
        }
        */
        for (int i = 0; i < v.size(); i++) {
            int r = v[i].R;
            int c = v[i].C;
            for (int i = 0; i < 4; i++) {
                int tr = r + dr[i];
                int tc = c + dc[i];
                if (tr < 0 || ROW <= tr || tc < 0 || COL <= tc) continue;
                if (chk[tr][tc] == 0 && im[r][c] > 0) im[r][c]--;
            }
        }
        
        if (ans == 0) puts("0"), is_end = true;
        else if (ans > 1) printf("%d\n", year), is_end = true;
        if (is_end) break;
        year++;
        memset(chk, 0, sizeof(chk));
    }
 
    return 0;
}