boj 2636 치즈

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

2636번: 치즈

판의 가장자리에는 치즈가 없기 때문에 0,0에서 bfs로 탐색하여 공기 부분을 체크를 합니다.

그 후에 반복문으로 치즈가 있는 위치에 인접한 좌표에 공기가 있으면 0으로 바꿔줍니다.

이 과정을 반복하여 치즈가 모두 녹아 없어지는 데 걸린 시간을 구하면서 1시간 전에 남아있는 치즈조각의 갯수를 출력합니다.

(치즈를 한번 녹였을 때 남아있는 치즈조각의 갯수를 계속해서 갱신합니다.)

 

 

[C++]

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
 
int list[100][100], N, M, pre, ans;
int direct[4][2] = { {0,1}, {1,0}, {0,-1}, {-1,0} };
bool visit[100][100];
 
void bfs() {
    memset(visit, false, sizeof(visit));
    queue<pair<int, int> > q;
    q.push({ 0,0 });
    visit[0][0] = true;
 
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
 
        for (int i = 0; i < 4; i++) {
            int nx = x + direct[i][0];
            int ny = y + direct[i][1];
 
            if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
            if (list[nx][ny] || visit[nx][ny]) continue;
 
            q.push({ nx,ny });
            visit[nx][ny] = true;
        }
    }
}
 
void func() {
    ans = pre;
    for (int i = 0; i <= N; i++) {
        for (int j = 0; j <= M; j++) {
            if (!list[i][j]) continue;
 
            for (int k = 0; k < 4; k++) {
                int nx = i + direct[k][0];
                int ny = j + direct[k][1];
 
                if (visit[nx][ny]) {
                    list[i][j] = 0;
                    ans--;
                    break;
                }
            }
        }
    }
}
 
void input() {
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> list[i][j];
            if (list[i][j]) pre++;
        }
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    if (!pre) cout << "0\n0\n";
    for (int T = 1; pre ; T++) {
        bfs();
        func();
        if (!ans) {
            cout << T << '\n' << pre << '\n';
            break;
        }
 
        pre = ans;
    }
 
    return 0;
}

 

 

[Java]

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int list[][] = new int[101][101];
    static boolean visit[][] = new boolean[101][101];
    static int direct[][] = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
    static int N, M, cnt;
 
    static void removeCheese() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (list[i][j] == 1) {
                    boolean chk = false;
                    for (int d = 0; d < 4; d++) {
                        int nx = i + direct[d][0];
                        int ny = j + direct[d][1];
 
                        if (visit[nx][ny]) {
                            chk = true;
                            break;
                        }
                    }
 
                    if (chk) {
                        list[i][j] = 0;
                        cnt--;
                    }
                }
            }
        }
    }
 
    static void bfs() {
        Deque<int[]> dq = new ArrayDeque<>();
        dq.add(new int[] { 0, 0 });
        visit[0][0] = true;
 
        while (!dq.isEmpty()) {
            int x = dq.peek()[0];
            int y = dq.poll()[1];
 
            for (int i = 0; i < 4; i++) {
                int nx = x + direct[i][0];
                int ny = y + direct[i][1];
 
                if (nx < 0 || ny < 0 || nx >= N || ny >= M)
                    continue;
                if (visit[nx][ny] || list[nx][ny] == 1)
                    continue;
 
                dq.add(new int[] { nx, ny });
                visit[nx][ny] = true;
            }
        }
    }
 
    static void init() {
        for (int i = 0; i < N; i++) {
            Arrays.fill(visit[i], false);
        }
    }
 
    static void func() {
        int pre = cnt;
        for (int t = 1;; t++) {
            bfs();
            removeCheese();
            init();
            if (cnt == 0) {
                System.out.println(t);
                System.out.println(pre);
                return;
            }
            pre = cnt;
        }
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                list[i][j] = Integer.parseInt(st.nextToken());
                if (list[i][j] == 1)
                    cnt++;
            }
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
    }
}