[JAVA] BOJ 백준 2638번 - 치즈

목차

• 문제
• 내가 푼 방법
• 자바 코드
• 결과 및 회고

---

1. 문제

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

2638번: 치즈

---

2. 내가 푼 방법

BFS 알고리즘을 이용해 모눈종이 가장자리처럼 치즈가 아닌 부분을 이동하면서 상하좌우에 +1씩 더해주었다. 그렇게 되면, 공기와 접촉한 부분을 알 수 있으므로 치즈 임과 동시에 2 이상일 경우에 치즈를 녹여주면 된다.

Queue<Tuple> queue = new LinkedList<>();
boolean[][] visit = new boolean[N][M];
int[][] around = new int[N][M];
int[] dx = {-1, 0, 1, 0};
int[] dy = {0, -1, 0, 1};

queue.add(new Tuple(0, 0));
visit[0][0] = true;

while (!queue.isEmpty()) {
    Tuple t = queue.poll();
    int x = t.x;
    int y = t.y;

    for (int i = 0; i < dx.length; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];

        if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
        around[nx][ny]++;
        if (visit[nx][ny] || arr[nx][ny] == 1) continue;

        visit[nx][ny] = true;
        queue.add(new Tuple(nx, ny));
    }
}

---

3. 자바 코드

깃허브 풀이 주소 : https://github.com/geujeog/BOJ/blob/main/B2638.java

import java.util.*;
import java.io.*;

class Main {
    static int N, M;
    static int[][] arr;
    static int result;

    public static void main (String[] args) throws IOException {
        input();
        solution();
        output();
    }

    public static void solution() {
        while (melt()) {
            result++;
        }
    }

    public static boolean melt() {
        Queue<Tuple> queue = new LinkedList<>();
        boolean[][] visit = new boolean[N][M];
        int[][] around = new int[N][M];
        int[] dx = {-1, 0, 1, 0};
        int[] dy = {0, -1, 0, 1};

        queue.add(new Tuple(0, 0));
        visit[0][0] = true;

        while (!queue.isEmpty()) {
            Tuple t = queue.poll();
            int x = t.x;
            int y = t.y;

            for (int i = 0; i < dx.length; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];

                if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
                around[nx][ny]++;
                if (visit[nx][ny] || arr[nx][ny] == 1) continue;

                visit[nx][ny] = true;
                queue.add(new Tuple(nx, ny));
            }
        }

        boolean isMelt = false;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (arr[i][j] == 1 && around[i][j] >= 2) {
                    isMelt = true;
                    arr[i][j] = 0;
                }
            }
        }

        return isMelt;
    }

    public static class Tuple {
        int x;
        int y;

        public Tuple(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public static void output() throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        bw.write(result+"");

        bw.flush();
        bw.close();
    }

    public static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        arr = new int[N][M];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());

            for (int j = 0; j < M; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        br.close();
    }
}

---

4. 결과 및 회고

보자마자 어떻게 풀어야 할지 감이 잡혀서 바로 풀린 문제이다.