BOJ 2638: 치즈

문제 풀이

치즈가 전부 녹는데 걸리는 시간을 return 해주는 문제이다.
나는 치즈는 input을 받는 즉시 Queue에 넣어 지도를 전체 순회하지 않아도 추적할 수 있도록 했다.

• airCategory(), airChoose()
  치즈를 녹이는 공기는 치즈 내부에 있는 공기가 아닌 외부에 있는 공기만 해당된다.
  이를 구하기 위해 stack을 이용해 공기 덩이를 나눠 airMap에 저장해뒀다.
  문제 조건에 map의 가장자리에는 치즈가 안 놓이므로 map의 가장자리는 치즈 외부 공기임을 보장한다.
  그러므로 가장자리로 시작해 공기 덩이를 나누면 외부 공기가 먼저 저장되고 그 이후에 내부 공기를 순회하게 된다.

• melting()
  Queue 안의 치즈를 확인하면서 외부 공기와의 접촉만 확인하면 된다.

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

public class Main {
    static int N, M;
    static int[][] map;
    static Queue<CheseIndex> q = new LinkedList<>();
    public static void main(String[] args) 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());
        map = new int[N][M];

        for(int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < M; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if(map[i][j] == 1) {
                    q.add(new CheseIndex(i, j));
                }
            }
        }

        int year = 0;
        while(!q.isEmpty()) {
            airCategory();
            melting();
            year++;
        }
        System.out.println(year);
    }

    static int[][] airMap;
    static int[] dirI = {0, 0, 1, -1};
    static int[] dirJ = {1, -1, 0, 0};
    public static void airCategory() {
        airMap = new int[N][M];
        int number = 2;
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < M; j++) {
                if(map[i][j] == 0 && airMap[i][j] == 0) {
                    airChoose(number, new CheseIndex(i, j));
                    number++;
                }
            }
        }
    }
    public static void airChoose(int number, CheseIndex cur) {
        Stack<CheseIndex> s = new Stack<>();
        s.push(cur);
        while(!s.isEmpty()) {
            CheseIndex temp = s.pop();
            airMap[temp.i][temp.j] = number;
            for(int index = 0; index < 4; index++) {
                int nextI = temp.i + dirI[index];
                int nextJ = temp.j + dirJ[index];

                if(nextI < 0 || nextI >= N || nextJ < 0 || nextJ >= M) {
                    continue;
                }
                if(map[nextI][nextJ] == 0 && airMap[nextI][nextJ] == 0) {
                    s.add(new CheseIndex(nextI, nextJ));
                }
            }
        }
    }

    public static void melting() {
        int len = q.size();
        for(int i = 0; i < len; i++) {
            CheseIndex temp = q.poll();
            int count = 0;
            for(int index = 0; index < 4; index++) {
                int nextI = temp.i + dirI[index];
                int nextJ = temp.j + dirJ[index];
                if(airMap[nextI][nextJ] == 2) {
                    count++;
                }
            }
            if (count < 2) {
                q.add(temp);
            }
            else {
                map[temp.i][temp.j] = 0;
            }
        }
    }
}
class CheseIndex {
    int i;
    int j;

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

github
백준