[JAVA][BOJ][G4] 2638. 치즈

2638번: 치즈

문제

N×M의 모눈종이 위에 아주 얇은 치즈가 <그림 1>과 같이 표시되어 있다. 단, N 은 세로 격자의 수이고, M 은 가로 격자의 수이다. 이 치즈는 냉동 보관을 해야만 하는데 실내온도에 내어놓으면 공기와 접촉하여 천천히 녹는다. 그런데 이러한 모눈종이 모양의 치즈에서 각 치즈 격자(작 은 정사각형 모양)의 4변 중에서 적어도 2변 이상이 실내온도의 공기와 접촉한 것은 정확히 한시간만에 녹아 없어져 버린다. 따라서 아래 <그림 1> 모양과 같은 치즈(회색으로 표시된 부분)라면 C로 표시된 모든 치즈 격자는 한 시간 후에 사라진다.

<그림 1>

<그림 2>와 같이 치즈 내부에 있는 공간은 치즈 외부 공기와 접촉하지 않는 것으로 가정한다. 그러므 로 이 공간에 접촉한 치즈 격자는 녹지 않고 C로 표시된 치즈 격자만 사라진다. 그러나 한 시간 후, 이 공간으로 외부공기가 유입되면 <그림 3>에서와 같이 C로 표시된 치즈 격자들이 사라지게 된다.

<그림 2>

<그림 3>

모눈종이의 맨 가장자리에는 치즈가 놓이지 않는 것으로 가정한다. 입력으로 주어진 치즈가 모두 녹아 없어지는데 걸리는 정확한 시간을 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표시된다. 또한, 각 0과 1은 하나의 공백으로 분리되어 있다.

출력

출력으로는 주어진 치즈가 모두 녹아 없어지는데 걸리는 정확한 시간을 정수로 첫 줄에 출력한다.

풀이

조건만 잘 살핀다면 dfs와 사방탐색을 이용해 복잡하지 않게 풀 수 있다 중요한 조건은 1 치즈 내부에 있는 공간은 외부 공기로 계산하지 않는다 2 두 면 이상 맞닿아 있어야 녹는다 이렇게 두 가지다

처음에는 0(내부 공기), 1(치즈), 2(외부 공기)가 아닌, 외부공기를 나타내는 boolean 배열과 치즈를 나타내는 boolean 배열을 따로 썼더니 visited 배열까지 필요해지는 바람에 너무 복잡해 보여서 int 배열로 수정했다 그 이외에는 어려운 건 없었지만 외부 공기를 파악하는 사방탐색 알고리즘에서 visited를 초기화하지 않았더니 제대로 돌아가지 않았다 주의해야겠다

코드

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

public class G4_2638_치즈 {
	static int N, M, ans, arr[][];
	static boolean visited[][];
	static int[] dx = {-1, 1, 0, 0};
	static int[] dy = {0, 0, -1, 1};
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		arr = new int[N][M];
		
		int cheeze = 0;
		
		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());
				if(arr[i][j] == 1) cheeze++;
			}
		}

		cheeze(0, cheeze);
		
		System.out.println(ans);
	}

	private static void cheeze(int cnt, int cheeze) {
		if(cheeze <= 0) {
			ans = cnt;
			return;
		}
		
		visited = new boolean[N][M];
		isAir(0, 0);
		
		for (int i = 1; i < N-1; i++) {
			for (int j = 1; j < M-1; j++) {
				if(arr[i][j] == 1) {
					int melt = 0;
					
					for (int k = 0; k < 4; k++) {
						if(melt==2) break;
						
						int x = i+dx[k];
						int y = j+dy[k];
						
						if(visited[x][y]) melt++;
					}
					
					if(melt>=2) {
						arr[i][j] = 2;
						cheeze--;
					}
				}
			}
		}
		
		cheeze(cnt+1, cheeze);
		
	}

	private static void isAir(int i, int j) {
		visited[i][j] = true;
		arr[i][j] = 2;
		
		for (int k = 0; k < 4; k++) {
			int x = i+dx[k];
			int y = j+dy[k];
			
			if(x < 0 || x>=N || y<0 || y>=M || visited[x][y] || arr[x][y] == 1) continue;
			
			isAir(x, y);
		}
		
	}

}

결과

 

#자바 #java #boj #백준 #알고리즘