치즈

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

풀이

0,0부터 bfs를 통해 외부 공기만을 방문하도록 한다. 이렇게 하면 치즈로 쌓인 공기는 방문하지 않으므로 내부 공기와 외부 공기를 분리할 수 있다.

bfs로 탐색이 끝났다면 이제 치즈를 찾아 치즈 주변에 true인 영역이 2개 이상인지 파악하고 2개 이상이면 0으로 만든다.

마지막으로 전체 배열에 치즈가 남아있는지 검사하고 있다면 위의 과정을 반복하고 없다면 반복을 그만하고 이 시점의 cnt 값을 출력한다.

하지만 이렇게 풀이하면 알고리즘적으로는 문제가 없다. 하지만 bfs로 탐색하는 과정에서 큐에 중복된 좌표값이 들어가고 이는 메모리초과를 야기한다.

따라서 중복된 좌표가 큐에 들어가지 않게 해야한다. 그래서 큐에 한번 들어간 좌표의 값을 2로 바꿔 중복된 좌표가 큐에 들어가지 않게 처리했고 위의 과정을 반복하기 전에 2로 바꾼 좌표의 값을 다시 0으로 돌리는 과정을 추가했다.

코드

import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    static int[] dx = {-1, 0, 0, 1};
    static int[] dy = {0, -1, 1, 0};
    static int n, m;
    static short[][] arr;
    static boolean[][] visit;
    static Queue<Pair> queue;
    static ArrayList<Pair> cheese;

    public static void main(String[] args) throws IOException {
        // write your code here
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] input = br.readLine().split(" ");
        n = Integer.parseInt(input[0]);
        m = Integer.parseInt(input[1]);
        arr = new short[n][m];
        cheese = new ArrayList<>();
        queue = new LinkedList<>();
        visit = new boolean[n][m];

        for (int i = 0; i < n; i++) {
            String[] line = br.readLine().split(" ");
            for (int j = 0; j < m; j++) {
                arr[i][j] = Short.parseShort(line[j]);
            }
        }
        int cnt = 0;
        while (true) {
            bfs();
            isCheeseMelt(visit);
            boolean flag = isCheese();
            cnt++;
            if (!flag)
                break;
        }
        System.out.println(cnt);
        bw.close();
        br.close();
    }

    private static void bfs() {
        resetVisit();
        queue.clear();
        queue.offer(new Pair((short) 0, (short) 0));

        while (!queue.isEmpty()) {
            Pair p = queue.poll();
            visit[p.x][p.y] = true;
            for (int i = 0; i < 4; i++) {
                short nx = (short) (p.x + dx[i]);
                short ny = (short) (p.y + dy[i]);
                if ((nx >= 0 && nx < n) && (ny >= 0 && ny < m) && !visit[nx][ny]) {
                    if (arr[nx][ny] == 0) {
                        arr[nx][ny] = 2;
                        queue.offer(new Pair(nx, ny));
                    }
                }
            }
        }
    }

    private static void resetVisit() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++)
                visit[i][j] = false;
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if(arr[i][j] == 2)
                    arr[i][j] = 0;
            }
        }
    }

    private static void isCheeseMelt(boolean[][] visit) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (arr[i][j] == 1) {
                    int cnt = 0;
                    for (int k = 0; k < 4; k++) {
                        int nx = i + dx[k];
                        int ny = j + dy[k];
                        if (visit[nx][ny])
                            cnt++;
                    }
                    if (cnt >= 2)
                        arr[i][j] = 0;
                }
            }
        }
    }

    private static boolean isCheese() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (arr[i][j] == 1)
                    return true;
            }
        }
        return false;
    }
}

class Pair {
    public short x;
    public short y;

    public Pair(short x, short y) {
        this.x = x;
        this.y = y;
    }
}