백준 2636, 2638 치즈 (Java)

1. 문제 링크

2638번: 치즈

 

2. 문제 및 입출력예제

 

3. 문제 풀이

1. 입력받으면서 전체 치즈의 수를 셌고 치즈가 다 녹으면 끝이 난다.
2. find()로 DFS 하면서 외부 좌표는 out 배열에 저장했다.
3. 외부 좌표를 다 찾았으면 melt로 치즈를 녹인다.
4. melt()에서는 치즈가 나오면 out 배열의 값을 비교해서 두 변 이상이 외부에 노출되었다면 queue에 넣는다. (2638번)
5. melt 끝나고 오면 전체 치즈 수에서 큐의 크기를 빼고, 큐에서 빼서 현 좌표를 0으로 만들어 다음 find에서 외부로 취급하게 만든다.

 

 

 

4. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;

public class Main {
	static class Point {
		int x;
		int y;

		public Point(int x, int y) {
			super();
			this.x = x;
			this.y = y;
		}
	}

	static int N, M, map[][];
	static boolean[][] visit, out;
	static int[] dx = { -1, 1, 0, 0 };
	static int[] dy = { 0, 0, -1, 1 };
	static Queue<Point> queue = new ArrayDeque<>();

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String[] split = br.readLine().split(" ");
		N = Integer.parseInt(split[0]);
		M = Integer.parseInt(split[1]);
		map = new int[N][M];
		out = new boolean[N][M];
		int total=0;
		for (int i = 0; i < N; i++) {
			split = br.readLine().split(" ");
			for (int j = 0; j < M; j++) {
				map[i][j] = Integer.parseInt(split[j]);
				if(map[i][j] == 1) { //치즈 수 세기
					total++;
				}
			}
		}

		queue = new ArrayDeque<>();

		int count = 0;
		while(total != 0) { //치즈 다 녹으면 끝
			visit = new boolean[N][M];
			find(0, 0);
			melt();
			count++;
			int size = queue.size();
			total -= size;
			while(size>0) {
				Point p = queue.poll();
				map[p.x][p.y] = 0;
				size--;
			}	
		}
		System.out.println(count);
	}

	private static void find(int i, int j) { //dfs로 외부를 out에 넣기
		visit[i][j] = true;
		out[i][j] = true;
		for(int d=0;d<4;d++) {
			int x = i+dx[d];
			int y = j+dy[d];
			if(x<0 || x>=N || y<0 || y>=M || visit[x][y] || map[x][y]==1) {
				continue;
			}
			find(x, y);
		}
	}

	private static void melt() { //out 비교해서 녹는 치즈 찾기
		for(int i=0;i<N;i++) {
			for(int j=0;j<M;j++) {
				if(map[i][j] == 0) {
					continue;
				}
				int temp = 0;
				for (int d = 0; d < 4; d++) {
					int X = i + dx[d];
					int Y = j + dy[d];
					if (0 <= X && X < N && 0 <= Y && Y < M && out[X][Y]) {
						temp++;
					}
				}
				if (temp >= 2) { //2보다 크면 녹는다
					queue.offer(new Point(i, j));
					System.out.println(i+" "+j);
					
				}
			}
		}
	}
}