BOJ 2638 - 치즈(Java)

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

2638번: 치즈

 

풀이

매 시간마다 외부 공기와 2변 이상 접촉하면 해당 위치의 치즈가 녹음

 

외부 공기 판별

    가장자리에는 치즈가 없다. -> 모든 가장자리는 외부 공기

    (0, 0)의 위치로 부터 시작 해서 치즈를 만나지 않는 위치로 dfs 탐색을 이용하여 외부 공기 판별 가능

private static void checkExternalAir(int i, int j) {
	visit[i][j] = true;
	air[i][j]=true;
	for (int d = 0; d < 4; d++) {
		int ny = i + dy[d];
		int nx = j + dx[d];
			
		if ((ny < 0 || nx < 0 || ny >= N || nx >= M) || visit[ny][nx] || cheese[ny][nx]) continue;
		checkExternalAir(ny, nx);
	}
}

 

치즈가 녹는지 확인

    모든 치즈의 위치를 확인, 현재 위치가 2변 이상 외부 공기와 접하면 List에 위치를 추가(한번에 없애기 위함)

    모든 탐색이 끝난 후 List의 크기 만큼 치즈의 개수를 감소, 해당 위치의 치즈를 없앰

private static void meltingCheese() {
	List<Pair> meltingPos = new ArrayList<>();
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (!cheese[i][j]) continue;

			if (isMelting(i, j)) {
				meltingPos.add(new Pair(i, j));
			}
		}
	}
        
	for (Pair pair : meltingPos) {
		cheeseCnt--;
		cheese[pair.y][pair.x] = false;
	}
}

 

전체 코드

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

public class Main {
    static int N, M;
    static boolean[][] air;
    static boolean[][] cheese;
    static boolean[][] visit;
    static int cheeseCnt = 0;
    static int[] dy = {0, 1, 0, -1};
    static int[] dx = {1, 0, -1, 0};

    static class Pair {
        public int y;
        public int x;

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

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        cheese = new boolean[N][M];
        air = new boolean[N][M];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                int temp = Integer.parseInt(st.nextToken());
                if (temp == 1) {
                    cheeseCnt++;
                    cheese[i][j] = true;
                } else {
                    cheese[i][j] = false;
                }
            }
        }
        int time = 0;
        while (cheeseCnt != 0) {
            visit = new boolean[N][M];
            // 가장 자리에는 치즈가 놓이지 않는다. 즉 (0,0)과 이어지는 공기는 외부 공기
            checkExternalAir(0, 0);
            meltingCheese();
            time++;
        }
        System.out.println(time);
    }

    // dfs를 이용해 (0, 0)에서 부터 외부 공기 탐색
    private static void checkExternalAir(int i, int j) {
        visit[i][j] = true;
        air[i][j]=true;
        for (int d = 0; d < 4; d++) {
            int ny = i + dy[d];
            int nx = j + dx[d];
            if ((ny < 0 || nx < 0 || ny >= N || nx >= M) || visit[ny][nx] || cheese[ny][nx]) continue;
            checkExternalAir(ny, nx);
        }
    }

    // 모든 위치 탐색, 치즈가 있는 장소라면 현재 시점에서 녹는 치즈인지 확인
    private static void meltingCheese() {
        List<Pair> meltingPos = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (!cheese[i][j]) continue;

                if (isMelting(i, j)) {
                    // 외부 공기 접촉으로 녹는다면 List에 추가
                    meltingPos.add(new Pair(i, j));
                }
            }
        }
        // 현재 시점에서 녹는 치즈 List 처리
        for (Pair pair : meltingPos) {
            cheeseCnt--;
            cheese[pair.y][pair.x] = false;
        }
    }

    // 현재 위치의 치즈가 녹는지 확인
    private static boolean isMelting(int i, int j) {
        int cnt = 0;
        // 인근 위치 확인 외부공기와 맞닿는 부분이 2개 이상이면 return true
        for (int d = 0; d < 4; d++) {
            int ny = i + dy[d];
            int nx = j + dx[d];
            if (air[ny][nx])
                cnt++;
            if(cnt>=2){
                return true;
            }
        }
        return false;
    }
}