[BaekJoon][2636] 치즈

BAEKJOON ONLINE JUDGE

한국정보올림피아드 2000

2636 치즈

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

공기와의 접촉면 -> 한 시간 후 녹아 없어짐 -> 공기로 됨

구멍 -> 공기처럼 치즈를 녹이진 않음. but 공기와 만나면 공기가 됨

1. input 받고, 구멍과 공기를 구분 -> labeling

2_1. 공기와 닿은 면적 공기로 만들기 -> 반복문

2_2. 공기와 구멍이 만나면 구멍도 공기로 만들기 -> dfs

#include <stdio.h>
 
int width, height;
int map[101][101];
int label[101][101][2];
int full;
int dy[4] = { -1, 0, 0, 1 };
int dx[4] = { 0, -1, 1, 0 };
 
void input()
{
    int i, j;
 
    scanf("%d %d", &height, &width);
 
    for (i = 0; i < height; i++) {
        for (j = 0; j < width; j++) {
            scanf("%d", &map[i][j]);
 
            if (map[i][j])    full++;
        }
    }
}
 
void dfs(int y, int x)
{
    int i, nexty, nextx;
 
    for (i = 0; i < 4; i++) {
        nexty = y + dy[i];
        nextx = x + dx[i];
 
        if (nexty >= 0 && nexty < height && nextx >= 0 && nextx < width) {
            if (label[nexty][nextx][0] == 0 && map[nexty][nextx] == 0) {
                label[nexty][nextx][0] = label[y][x][0];
                dfs(nexty, nextx);
            }
        }
    }
}
 
void labeling()
{
    int i, j;
    int cnt = 1;
 
    for (i = 0; i < height; i++) {
        for (j = 0; j < width; j++) {
            if (map[i][j] == 0 && label[i][j][0] == 0) {
                label[i][j][0] = cnt++;
                dfs(i, j);
            }
        }
    }
}
 
void air(int y, int x, int flag, int num)
{
    int i, nexty, nextx;
 
    for (i = 0; i < 4; i++) {
        nexty = y + dy[i];
        nextx = x + dx[i];
 
        if (nexty >= 0 && nexty < height && nextx >= 0 && nextx < width) {
            if (label[nexty][nextx][flag] == num && label[nexty][nextx][!flag] != 1) {
                label[nexty][nextx][!flag] = 1;
                air(nexty, nextx, flag, num);
            }
        }
    }
}
 
void go()
{
    int i, j, k;
    int y, x;
    int flag = 0, cnt, count = full, time = 0;
 
    while (count > 0) {
        cnt = 0;
        for (i = 0; i < height; i++) {
            for (j = 0; j < width; j++) {
 
                label[i][j][!flag] = label[i][j][flag];
 
                if (label[i][j][flag] == 0) {
                    for (k = 0; k < 4; k++) {
                        y = i + dy[k];
                        x = j + dx[k];
 
                        if (y >= 0 && y < height && x >= 0 && x < width && label[y][x][flag] == 1) {
                            label[i][j][!flag] = 1;
                            cnt++;
                            break;
                        }
                    }
                }
            }
        }
 
        for (i = 0; i < height; i++) {
            for (j = 0; j < width; j++) {
 
                if (label[i][j][flag] != 1)
                    label[i][j][flag] = label[i][j][!flag];
 
                if (label[i][j][!flag] > 1) {
                    for (k = 0; k < 4; k++) {
                        y = i + dy[k];
                        x = j + dx[k];
 
                        if (y >= 0 && y < height && x >= 0 && x < width && label[y][x][!flag] == 1) {
                            air(i, j, !flag, label[i][j][!flag]);
                            break;
                        }
                    }
                }
            }
        }
 
        time++;
 
        if (cnt >= count)    break;
        count -= cnt;
    }
 
    printf("%d\n%d\n", time, count);
}
 
int main()
{
    input();
 
    labeling();
 
    go();
 
    return 0;
}