백준 2638 - 치즈

Java

2638 번 - 치즈

문제

접근 방법

BFS를 사용하여 치즈가 없는 빈 공간이 외부인지 내부인지 확인한다.
문제에서 ‘모눈종이의 맨 가장자리에는 치즈가 놓이지 않는 것으로 가정’하므로,
(0,0) 점에서 시작하여 치즈로 막혀있지 않는 모든 곳을 탐색하면, 외부를 찾을 수 있다.

이후 n * m 공간을 탐색하며 치즈가 있을 시, 2개 이상의 외부가 존재 여부를 확인하여 치즈를 지운다.

코드

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

public class Main {
	static int n, result, m;
	static int totalC;
	static int[][] map;
	static boolean[][] isOut;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk = new StringTokenizer(br.readLine());
    	n = stoi(stk.nextToken());
    	m = stoi(stk.nextToken());

    	map = new int[n][m];

    	for(int i = 0; i < n; i++) {
    		stk = new StringTokenizer(br.readLine());
    		for(int j = 0; j < m; j++) {
    			map[i][j] = stoi(stk.nextToken());
    			if(map[i][j] == 1)
    				totalC++;
    		}
    	}

    	int curCh = 0, turn = 0, ny, nx, cntOut;
    	// 치즈가 다 녹을 때 까지 진행
    	while(curCh != totalC) {

    		isOut = new boolean[n][m];
    		BFS();

    		for(int y = 0; y < n; y++) {
    			for(int x = 0; x < m; x++) {
    				// 해당 위치에 치즈가 있을 때
    				if(map[y][x] == 1) {
    					cntOut = 0;
    					// 해당 위치의 상하좌우가 외부 일 시
    					for(int i = 0; i < 4; i++) {
    						ny = y + dy[i];
    						nx = x + dx[i];
    						if(isOut[ny][nx]) {
    							cntOut++;
    						}
    					}

    					// 외부가 2개 이상일 때
    					if(cntOut >= 2) {
    						map[y][x] = 0;	// 이 장소의 치즈는 사라진다.
    						curCh++;
    					}
    				}
    			}
    		}

    		turn++;
    	}

    	System.out.println(turn);
    	br.close();
	}

	static int[] dy = {-1, 1, 0, 0};
	static int[] dx = {0, 0, -1, 1};

	// 빈 공간이 외부인지 확인하는 메서드
	private static void BFS() {

		Queue<int[]> queue = new LinkedList<>();
		int[] q;
		int y,x, ny, nx;
		queue.add(new int[] {0,0});
		isOut[0][0] = true;
		while(!queue.isEmpty()) {
			q = queue.poll();

			y = q[0];
			x = q[1];

			for(int i = 0; i < 4; i++) {
				ny = y + dy[i];
				nx = x + dx[i];
				if(isIn(ny,nx) && !isOut[ny][nx] && map[ny][nx] == 0) {
					isOut[ny][nx] = true;
					queue.add(new int[] {ny, nx});
				}
			}
		}
	}


	// 주어진 범위 안에 있는가
    public static boolean isIn(int y, int x){
        if(y < 0 || y >= n || x < 0 || x >= m)
            return false;
        return true;
    }
	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}