[BAEKJOON] 치즈

 

---

원래 치즈 모양과 예제 입력에서 치즈 내부의 구멍이 있는 '0'인 곳은 공기로 보면 안 된다.

치즈가 아닐 뿐 외부 공기와 맞닿아 있지 않았기 때문이다.

또한, 예제 입력에서 판의 가장자리에는 치즈가 놓여있지 않다고 하니 외부 공기로 판단하여 bfs 혹은 dfs로 가장 겉부분의 치즈만 파악할 수 있다면 모든 치즈가 녹는 데까지 시간을 구할 수 있을 것이다.

시간이 1씩 증가할 때마다 공기의 상, 하, 좌, 우 방향으로 겉부분의 치즈를 공기에 노출되게끔 한다.

 

모든 치즈가 사라지기 전의 시간을 출력해야하므로 매 시간이 흐를 때마다 먼저 치즈의 전체 개수를 세고, 외부 공기를 맞닿게 하는 순서로 진행한다.

[BFS 풀이]

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

public class Main_BFS {
	static int N, M, answer, time;
	static int[][] arr, dir = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
	static Queue<Point> air = new ArrayDeque();
	boolean[][] visit = new boolean[N][M];

	public static void main(String[] args) throws NumberFormatException, 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());
		arr = new int[N][M];
		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) {
					answer++;
				}
				if ((i == 0 || i == N - 1) && arr[i][j] == 0) {
					arr[i][j] = -1; // 외부 공기인 것은 -1 처리 
					air.add(new Point(i, j));
				}
				if ((j == 0 || j == M - 1) && arr[i][j] == 0) {
					arr[i][j] = -1;
					air.add(new Point(i, j));
				}
			}
		}
		go();
		System.out.println(time + "\n" + answer);
	}

	private static void go() {
		int result = countCheese(); // 첫 치즈 큐에 넣기
		if (result == 0) {
			return;
		}
		time++;
		while (true) {
			count();
			result = countCheese();
			if (result == 0) { // 다음 단계로 갈 수 없다면
				break;
			}
			answer = result;
			time++;
		}
	}

	private static void count() {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (arr[i][j] == 2)
					air.offer(new Point(i, j));
			}
		}
	}

	private static int countCheese() { // 치즈 만나면 2로 바꾸기
		int sum = 0;
		while (!air.isEmpty()) {
			Point now = air.poll();
			int x = now.x;
			int y = now.y;
			for (int d = 0; d < 4; d++) {
				int nx = x + dir[d][0];
				int ny = y + dir[d][1];
				if (nx < 0 || ny < 0 || nx >= N || ny >= M)
					continue; // 맞닿은 게 치즈가 아니라면 넘어가기
				if (arr[nx][ny] == 0) {
					arr[nx][ny] = -1; // 외부 공기로 간주하여 -1 처리
					air.offer(new Point(nx, ny));
				}
				if (arr[nx][ny] == 1) {
					arr[nx][ny] = 2;
					sum++;
				}
			}
		}
		return sum;
	}

	private static class Point {
		int x, y;

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

		@Override
		public String toString() {
			return "Point [x=" + x + ", y=" + y + "]";
		}
	}
}

 

[DFS 풀이]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main_DFS {
	static int N, M, answer, time;
	static int[][] arr, dir = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
	static boolean[][] visit;

	public static void main(String[] args) throws NumberFormatException, 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());
		arr = new int[N][M];
		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) {
					answer++;
				}
			}
		}
		go();
		System.out.println(time + "\n" + answer);
	}

	private static void go() {
		while (true) {
			int cnt = count();
			if (cnt == 0) {
				break;
			}
			visit = new boolean[N][M];
			countCheese(0, 0);
			answer = cnt;
			time++;
		}
	}

	private static int count() {
		int cnt = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (arr[i][j] == 1)
					cnt++;
			}
		}
		return cnt;
	}

	private static void countCheese(int x, int y) {
		for (int d = 0; d < 4; d++) {
			int nx = x + dir[d][0];
			int ny = y + dir[d][1];
			if (nx < 0 || ny < 0 || nx >= N || ny >= M)
				continue; // 맞닿은 게 치즈가 아니라면 넘어가기

			if (!visit[nx][ny]) {
				visit[nx][ny] = true;
				if (arr[nx][ny] == 0) {
					countCheese(nx, ny);
				} else {
					arr[nx][ny] = 0;
				}
			}
		}
	}
}

[출처]

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

2636번: 치즈