[2573] 빙산

https://www.acmicpc.net/problem/2573

2573번: 빙산

<문제>

플러드필같은 느낌의 bfs 문제이다.

이 문제는 호수와 바다의 구분이 존재하지 않지만, 비슷한 문제인 "[2636]치즈"의 경우 호수와 바다를 구분한다.

기본적으로 모든칸을 순회하며, 아직 방문하지 않았으면서 빙산인 정점을 시작으로 bfs를 진행한다.

하나의 턴에 여러번의 bfs가 진행될 수 있다. 이는 빙산이 쪼개진 경우에 해당한다.

 

bfs 탐색에서 구현해야 하는건 아래와 같다.

1. 현재 정점에서, 인접한 정점이 방문하지 않은 빙산이라면 이를 queue에 push해야한다.

2. 인접한 정점이 방문하지 않은 바다라면, 별도로 카운팅해주어 빙산을 카운트된만큼 녹여야한다.

바다는 당연히 탐색대상이 아니므로 방문하지 않았다는 표시를 놓치기 쉬운데,

이경우 같은턴에 빙산이였지만 한번에 녹아버려 바다가된 빙산이

인접한 빙산에 연쇄적으로 영향을 미치는 오류가 발생한다.

 

이 오류는 예제 1번의 가장 왼쪽 위 빙산(2행 2열)이, 오른쪽 빙산인 2행 3열에 영향을 주는것을 확인하면 된다.

1턴이 지나고 예제1의 2행 3열빙산이 4->2로 되어야 하지만,

4->1로 되어버리는 오류는 바다에 대해서 방문확인을 안해서 생긴 오류이다.

 

고로, 인접한 정점이 빙산이든 바다이든 항상 visit을 먼저 확인해주어야 한다.

 

<소스코드>

#include <stdio.h>
#include <string.h>
 
#include <algorithm>
#include <queue>
using namespace std;
int n, m, a[301][301];
int dy[4] = {0, 1, 0, -1}, dx[4] = {1, 0, -1, 0};
bool check[301][301];
void bfs(int sy, int sx) {
    queue<int> q;
    int y, x, ty, tx, i, near_sea = 0;
    check[sy][sx] = true;
    q.push(sy);
    q.push(sx);
    while (!q.empty()) {
        near_sea = 0;
        ty = q.front();
        q.pop();
        tx = q.front();
        q.pop();
        for (i = 0; i < 4; i++) {
            y = ty + dy[i];
            x = tx + dx[i];
            if (y < 0 || x < 0 || y >= n || x >= m) continue;
            if (a[y][x] == 0 && check[y][x] == false) {
                near_sea++;
            }
            if (check[y][x] == false && a[y][x] > 0) {
                q.push(y);
                q.push(x);
                check[y][x] = true;
            }
        }
        a[ty][tx] = max(0, a[ty][tx] - near_sea);
    }
}
int main(void) {
    int i, j, cnt = 0, year = 0;
    bool div = false;
    bool key_0;
    scanf("%d %d", &n, &m);
    for (i = 0; i < n; i++)
        for (j = 0; j < m; j++) scanf("%d", &a[i][j]);
    while (1) {
        year++;
        memset(check, false, sizeof(check));
        cnt = 0;
        div = false;
        key_0 = true;
        for (i = 0; i < n; i++) {
            for (j = 0; j < m; j++) {
                if (check[i][j] == false && a[i][j] > 0) {
                    key_0 = false;
                    cnt++;
                    if (cnt >= 2) {
                        div = true;
                        break;
                    }
                    bfs(i, j);
                }
            }
            if (div) break;
        }
        if (key_0) {
            printf("0");
            return 0;
        } else if (div == true) {
            printf("%d", year - 1);
            return 0;
        }
    }
    return 0;
}