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

 

www.acmicpc.net/problem/2573

2573번: 빙산

DFS 또는 BFS를 이용할 수 있는데, DFS를 이용했다.

 

다음 과정을 계속 반복시킨다.

• check, vis 등 배열 및 변수 초기화

1. 빙산의 개수를 count 한다. (cnt변수 이용)
2. cnt값을 확인하여 2개이상인지? 아니면 0인지? (탈출 조건 확인)
   • 2 이상이면 조건을 만족했으므로 flag = true
   • 0이면 빙산이 다 녹았기 때문에 0을 출력해야 함.
3. checkSide() - 각 칸마다 바닷물에 접해있는 부분의 개수를 check 한다.
4. melt() - 바닷물에 접해있는 부분만큼 각 칸을 녹여준다.
5. 1년이 지났으므로 result++

반복문을 탈출했다면 flag 값에 따라서 빙하가 다 녹았는지? 아니면 분리되었는지 알 수 있기 때문에 flag를 확인하고 결과를 출력한다. 

 

 

 

소스코드

#include <bits/stdc++.h>
using namespace std;

int n, m, cnt, result, flag;
int g[300][300];
int check[300][300];
int vis[300][300];
int d[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; 

void checkSide() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (g[i][j] == 0) continue;

            for (int k = 0; k < 4; k++) {
                int x = i + d[k][0];
                int y = j + d[k][1];

                if (!g[x][y]) check[i][j]++; // 옆이 바다면 check 1증가
            }
        }
    }
}

void melt() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (g[i][j] && check[i][j])
                g[i][j] = max(0, g[i][j] - check[i][j]); // 뺀 값이 0보다 작아지면 안됨
        }
    }
}

void dfs(int x, int y) {
    vis[x][y] = 1;

    for (int i = 0; i < 4; i++) {
        int nx = x + d[i][0];
        int ny = y + d[i][1];

        if (!vis[nx][ny] && g[nx][ny])
            dfs(nx, ny);
    }
}

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> g[i][j];

    while (true) {
        memset(check, 0, sizeof(check));
        memset(vis, 0, sizeof(vis));
        cnt = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!vis[i][j] && g[i][j]) {
                    dfs(i, j);
                    cnt++;
                }
            }
        }
        if (cnt == 0) break; // 다 녹음
        if (cnt >= 2) { // 분리됨
            flag = 1;
            break;
        }
        checkSide();
        melt();
        result++;
    }
    if (flag) cout << result;
    else cout << 0;
    return 0;
}