BOJ 2638 치즈

www.acmicpc.net/problem/2638

2638번: 치즈

 

 

문제 분석

- BOJ 2636 치즈의 응용문제이다.

- 치즈와 관련되어 추가된 조건(2면이 닿았을 경우)을 bfs탐색시 추가해준다. 

 

 

문제 풀이

1) 맵의 상태를 입력받는다.

2) bfs탐색을 통해서 치즈가 닿는 부분을 확인한다.

3) 공기를 지나갔을 경우 visited판단은 맵의 값을 -1로 바꾼다.

4) 만약에 공기와 닿은 치즈의 경우 값을 3으로 바꿔준다. 

- 공기는 0에서 -1로 방문처리하고, 1은 공기와 닿지않은 치즈가 있는 부분, 2는 공기와 닿는 테두리의 치즈를 의미한다. 3은 공기와 닿는 면이 2면일 경우 녹여야 되는 치즈로 표시해준다. 

5) 맵을 처리해주면 이제 치즈의 개수를 확인하러 간다.

6) 치즈가 -1이나 3인 경우 0으로 바꿔주고(재방문 하라), 2인 경우(치즈부분이다) 1로 바꿔준다. 만약 1인 경우 치즈의 갯수를 증가시키고, 치즈가 0이라면 false값을 반환한다.

7) 시간을 증가시키고 치즈가 남아있다면 다시 치즈를 녹이러 간다. (재귀)

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.StringTokenizer;

public class Main {
	private static int R, C, time, temp, ans;
	private static int[] dr = { -1, 1, 0, 0 }; // 상하좌우 행
	private static int[] dc = { 0, 0, -1, 1 }; // 상하좌우 열
	private static int[][] map;
	private static Deque<Point> cheeseDq; // 치즈 좌표값 저장하는 큐

	public static void main(String[] args) throws Exception {
		input();
	}// main

	private static void input() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		st = new StringTokenizer(br.readLine());

		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());

		map = new int[R][C];
		ans = Integer.MAX_VALUE;
		cheeseDq = new ArrayDeque<>();

		for (int i = 0; i < R; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < C; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		} // 좌표값 입력
		meltCheese(0, 0);

		System.out.println(time + 1);

	}// input

	private static void meltCheese(int x, int y) {
		cheeseDq = new ArrayDeque<>();
		cheeseDq.add(new Point(x, y));
		map[x][y] = -1;
		while (!cheeseDq.isEmpty()) {

			Point cur = cheeseDq.poll();
			int r = cur.x;
			int c = cur.y;
			for (int d = 0; d < 4; d++) {
				int nr = r + dr[d];
				int nc = c + dc[d];

				if (nr < 0 || nc < 0 || nr >= R || nc >= C)
					continue;
				if (map[nr][nc] == -1)
					continue;

				if (map[nr][nc] == 2) {
					map[nr][nc] = 3;
				}

				if (map[nr][nc] == 1) {
					map[nr][nc] = 2;
				} else if (map[nr][nc] == 0) {
					cheeseDq.add(new Point(nr, nc));
					map[nr][nc] = -1;
				}
			}
		} // while

		// 치즈 남은거 체크하기
		if (!countCheese())
			return;
		time++;
		// 다시 치즈 녹이기
		meltCheese(0, 0);

	}// bfs

	private static boolean countCheese() { // 공기 : -1, 공기 접촉 치즈 : 2, 녹여야될 치즈 : 3, 내부 치즈 : 1

		int cheese = 0;
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {

				if (map[i][j] == -1) {
					map[i][j] = 0;
				}
				if (map[i][j] == 2) {
					map[i][j] = 1;
				}

				if (map[i][j] == 3) {
					map[i][j] = 0;
				}
				
				if (map[i][j] == 1) {
					cheese++;
				}
			}
		}

		if (cheese == 0) {
			return false;
		}
		return true;
	}// countCheese

	static class Point {
		int x;
		int y;

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

}// class-End