[백준 Java] 2638 치즈

[문제 링크] boj 2638 치즈 골드 3 자바

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

2638번: 치즈

 

[생각 흐름]

init 함수에서 배열에서 바깥쪽을 모두 -1로 초기화하고 안쪽에 있는 것과 다르게 표기한다. 이때 만약 치즈가 있는 칸이 하나도 없다면 true를 리턴하여 더 이상 진행하지 않도록 해준다.

이후에 remove 함수에서 치즈가 있는 칸이라면 4면 중 2면이 -1로 노출되어 있는 치즈 인지 확인하고 노출되어있다면 본 배열의 값을 0으로 변경하여 치즈를 삭제한다. 

위 과정을 반복하며 init 함수에서 치즈가 더 이상 판별되었다면 멈추도록 구현하였다.

 

[자바 코드]

import java.awt.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    private static Queue<Point> queue = new LinkedList<>();
    private static int dirx[] = new int[]{-1, 1, 0, 0};
    private static int diry[] = new int[]{0, 0, -1, 1};

    private static int arr[][];
    private static int arr2[][];

    private static boolean init(){
        arr2 = new int[arr.length][arr[0].length]; //임시 저장용 배열
        boolean flag = true;
        queue.clear();
        queue.add(new Point(0,0));
        while (!queue.isEmpty()) {
            Point temp = queue.poll();
            int px = (int) temp.getX();
            int py = (int) temp.getY();
            for (int i = 0; i < 4; i++) {
                int nx = px + dirx[i];
                int ny = py + diry[i];
                //벗어남
                if (nx >= arr.length || nx < 0 || ny < 0 || ny >= arr[0].length) continue;
                //벽이면
                if (arr[nx][ny] == 1) {
                    flag = false; //부서지지 않은 치즈가 있다면 계속 진행 해야함
                    continue;
                }
                //방문안한 노드이면
                if (arr[nx][ny] == 0 && arr2[nx][ny] != -1) {
                    arr2[nx][ny] = -1;
                    queue.add(new Point(nx, ny));
                }
            }
        }
        return flag;
    }

    private static void remove(){
        for(int i=0;i<arr.length;i++){
            for(int j=0;j<arr[0].length;j++){
                if(arr[i][j]==1){// 치즈가 있다면
                    int temp =0;
                    for (int k = 0; k < 4; k++) {
                        int nx = i + dirx[k];
                        int ny = j + diry[k];
                        //벗어남
                        if (nx >= arr.length || nx < 0 || ny < 0 || ny >= arr[0].length) continue;
                        //방문안한 노드이면
                        if (arr2[nx][ny] == -1) temp++;
                    }
                    if(temp>=2) arr[i][j]=0; //두변이 노출 된 경우 본 배열을 변경
                }
            }
        }
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int 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());
            }
        }

        int day = 0;
        while(true){
            if(init())break;
            day++;
            remove();
        }

        System.out.println(day);

    }
}