[백준] 2638 : 치즈 (JAVA/자바)

문제

BOJ 2638 : 치즈 - https://www.acmicpc.net/problem/2638

풀이

외부 공기와 내부 공기를 어떻게 판단해야 할 지 고민을 많이 했던 문제다. 외부공기는 (0,0)위치부터 BFS로 탐색하면 구할 수 있다. 스터디원들이랑 얘기해보니 DFS로도 가능한 것 같다.

치즈가 한시간 뒤 녹을 건지는 상하좌우를 확인하여 외부 공기와 두개 면 이상 맞닿아있을 경우 녹을 치즈로 판단했다.

1. 외부 공기(==-1)를 판단한다.
2. 1시간 뒤 녹을 치즈라면 체크해둔다. (리스트에 담아둔다.)
3. 리스트에 담긴 위치를 공기(==0)으로 값을 바꾼다.
4. 1~3을 반복하면서 더 이상 녹을 치즈가 없다면(== 다 녹았다면) 종료한다.

구현에서 까다로웠던 점이 이미 외부 공기가 -1로 값이 들어가 있는 상태에서, 녹은 치즈를 바탕으로 다시 외부공기를 찾아줘야 한다는 점이었다. 초기 외부공기 판단 시 BFS 조건으로 상하좌우 값을 보며 옆 칸의 공기가 0이면 큐에 넣어주면서 탐색했는데, 다음 턴에 이미 -1로 값이 들어가 있기 때문에 BFS 탐색 조건에 맞지 않았다. 이에 대한 해결로는 visited[][]를 따로 선언해서 방문하지 않았고 && 옆 칸이 1이 아닌경우(==치즈가 아닌경우) 큐에 넣는 조건으로 해결하였다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class Main {

    static int[][] map;
    static boolean[][] visited;
    static int n;
    static int m;
    static int[] mi = {0, 0, 1, -1};
    static int[] mj = {1, -1, 0, 0};
    static ArrayList<Loc> cheese_melt;

    static class Loc{
        int i;
        int j;

        public Loc(int i, int j) {
            this.i = i;
            this.j = j;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] inputs = br.readLine().split(" ");
        n = Integer.parseInt(inputs[0]);
        m = Integer.parseInt(inputs[1]);

        map = new int[n][m];

        for (int i = 0; i < n; i++) {
            inputs = br.readLine().split(" ");
            for (int j = 0; j < m; j++) {
                map[i][j] = Integer.parseInt(inputs[j]);
            }
        }

        int time = 0;

        cheese_melt = new ArrayList<>();

        while(true){
            cheese_melt.clear();
            visited = new boolean[n][m];

            setExternalAir(); // -1은 외부 공기, 0은 내부 공기

            for (int i = 1; i < n-1; i++) {
                for (int j = 1; j < m-1; j++) {
                    if(map[i][j]==1){ // 치즈이면
                        if (isMelt(i,j)) { // 1시간 내에 녹을 치즈면 == 두 변이 외부 공기와 맞닿아있으면
                            cheese_melt.add(new Loc(i, j));
                        }
                    }

                }
            }

            // 더 이상 녹을 치즈가 없다 == 치즈가 다 녹았다 -> 종료!
            if(cheese_melt.size()==0) break;	

            // 겉 치즈 녹음
            for (Loc l : cheese_melt) {
                map[l.i][l.j] = 0;
            }

            time ++;
        }

        System.out.println(time);
    }

    public static boolean isMelt(int i, int j){
        int cnt = 0;
        for (int d = 0; d < 4; d++) { // 상하좌우 확인
            int ni = i + mi[d];
            int nj = j + mj[d];

            if(ni<0 || nj<0 || ni>n || nj>m) continue;

            if(map[ni][nj] == -1) cnt++;
        }
		
        // 두 면 이상 맞닿아있는지 true/false로 return
        return cnt >= 2;
    }

    public static void setExternalAir(){

        Queue<Loc> q = new LinkedList<>();

        q.add(new Loc(0, 0));
        map[0][0] = -1;

        while (!q.isEmpty()) {
            Loc now = q.poll();

            for (int d = 0; d < 4; d++) {
                int ni = now.i + mi[d];
                int nj = now.j + mj[d];

                if(ni<0 || nj<0 || ni>=n || nj>=m ) continue;

                if(visited[ni][nj] || map[ni][nj] == 1) continue;

                visited[ni][nj] = true;
                map[ni][nj] = -1; // 외부 공기는 -1로 초기화
                q.add(new Loc(ni, nj));

            }
        }
    }
}

정리

✔ 알고리즘 분류 - 구현, 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색, 시뮬레이션
✔ 난이도 - 🟡 Gold 4

🤦‍♀️ 오늘의 메모

• 신선한(?) 문제여서 어떻게 로직을 구성해야 할지 생각을 많이 하게 되었던 문제였다. 기본적인 문제는 웬만큼 풀어봤다고 생각했는데 이렇게 어떻게 풀어나갈지조차 떠오르지 않는 문제를 보니 더 열심히 해야겠다는 생각이 들었다!

참고 사이트

https://velog.io/@leeinae/Algorithm-%EB%B0%B1%EC%A4%80-2638-%EC%B9%98%EC%A6%88-java (visit 배열만 참고!)