BOJ 2636 치즈

www.acmicpc.net/problem/2636

2636번: 치즈

 

 

문제 분석

- bfs를 통해 문제를 풀어야 한다. 기존의 bfs는 내부에서 외부로 나가면서 진행했다면 이번엔 외부에서 전체 배열을 탐색하면서 치즈가 있는 곳까지 탐색해야 한다. 

- bfs로 치즈의 위치를 찾고, 외부에 닿는 치즈일 경우 해당 치즈를 처리해준다. 

- 치즈가 다 녹았을 경우 걸린 시간과 그 전에 남아있는 치즈의 수도 출력해야한다.

 

 

문제 풀이

1) 좌표값을 입력받는다.

2) bfs탐색을 통해 공기와 닿아있는 치즈를 탐색한다. 

- 공기(탐색한 부분)은 -1로, 공기와 닿은 치즈는 2로, 내부 치즈는 1로 처리되어있다.

3) 공기와 닿아있는 치즈를 만나면 해당 치즈를 2로 바꾸고, 만약 닿지 않은 공기부분이라면 큐에 넣고 계속 탐색한다.

4) 탐색을 전부 끝내고 맵의 값을 -1,1,2로 설정해주었다면 치즈 남은 부분을 체크한다.

5) 전체 맵을 탐색하면서 -1인 경우 다시 0으로 바꿔주고, 2인 경우도 0으로 바꿔준다. 1인 경우 치즈가 남아있기때문에 치즈의 갯수를 증가시킨다.

6) 만약 탐색을 끝낸 후 치즈가 남아있지 않았다면 메소드를 false로 반환하여 전체 진행을 종료시킨다. 

cf) 아래 테스트케이스처럼 한 번 돌았을 경우 치즈가 전부 사라져 정답에 초기값이 출력될 경우를 위해 temp변수를 통해서 남아있는 치즈를 저장시키고 한 번에 처리됐을 경우 해당 값을 출력해준다.

5 5

0 0 0 0 0

0 1 1 0 0

0 1 0 1 0

0 1 1 1 0

0 0 0 0 0

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);
		if((time+1)==1){
			ans=temp;
		}
		System.out.println(ans);
	}// 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] == 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() {

		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) {
					temp++;
					map[i][j] = 0;
				}
				if (map[i][j] == 1) {
					cheese++;
				}
			}
		}

		if (cheese == 0) {
			return false;
		}
		ans = Math.min(cheese, ans);
		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