[백준] JAVA - 2636. 치즈

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

2636번: 치즈

생각

외부 영역과 맞닿아있는 치즈의 경계를 매초마다 지운다음 치즈가 모두 녹기 직전 치즈의 개수와 직전 시간을 구하는 문제입니다.

 

처음에 경계 치즈를 어떻게 구해줄까 생각하다가 내부에서 외부기준으로 판별하는게 어려워질껏같아 반대로 외부에서 내부를 BFS 탐색으로 체크해줬더니 경계를 체크할 수 있었습니다.

 

1. (0,0)부터 치즈가 없는 외부 영역 (map[y][x] = 0) 을 기준으로 BFS 탐색을 시작합니다. 이때 visited 배열을 여기서 초기화해줘서 이전의 visited가 현재 탐색을 하는 과정에서 영향을 주면 안됩니다.

2. 인접한 영역이 방문하지않았고 치즈라면 방문체크와 경계 치즈의 좌표를 넣어줍니다.

3. 인접한 영역이 방문하지 않았고 치즈가 아니라면 방문체크와 큐에 다음 좌표를 추가해줍니다.

4. 한 step 이 끝났을 경우 경계 좌표에 저장된 치즈들을 모두 녹여줍니다. (map[y][x] = 0)

5. 미리 선언한 List<Integer[]> 타입인 area에 해당 시간과 녹여준 치즈의 개수를 add 해줍니다.

6. 1~5 작업을 녹일수 있는 치즈의 개수가 0이 될때까지 반복해줍니다.

Java Code

package com.java.algorithm;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

/*
치즈가 모두 없어지는데 걸리는시간, 모두 녹기 한시간전 치즈 개수
1. 경계에 있는 치즈 어떻게 찾아줄래? 밖에서부터 거꾸로 보자 map[y][x] == 0 일때 bfs로 찾는다
2. 경계값 좌표 따로 저장해주자. -> step 마다 묶어서 녹여주기 map[y][x] = 0 처리해준다
3. 녹는 치즈 개수 세줘서 [[time,cnt]] List<Integer[]> 2차원배열로 저장해준다.
*/

public class BOJ_2636_치즈 {
	static class Pos {
		int y;
		int x;
		public Pos(int y, int x) {
			super();
			this.y = y;
			this.x = x;
		}
		@Override
		public String toString() {
			return "Pos [y=" + y + ", x=" + x + "]";
		}
		
	}
	
	static int R,C;
	static int[][] map;
	static boolean[][] visited;
	static List<Integer[]> area;
	static int[] dy = {1,-1,0,0};
	static int[] dx = {0,0,-1,1};
	static int ans;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		map = new int[R][C];
		
		area = new ArrayList<Integer[]>();
		
		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());
			}
		}
		
		solve(0,0);
		for (int i = 0; i < area.size(); i++) {
			if(area.get(i)[1] == 0) {
				System.out.println(area.get(i-1)[0]);
				System.out.println(area.get(i-1)[1]);
			}
		}
		
	}
	//경계에 있는 치즈 찾아서 갯수 세고, 0 으로 바꿔놓기
	private static void solve(int i, int j) {
		ArrayList<Integer[]> deletePos; // step 마다 녹아야하는 경계 치즈 좌표들
		int cnt; // step 마다 녹는 치즈 개수
		int time = 0;
		while(true) {
			deletePos = new ArrayList<>();
			Queue<Pos> q = new LinkedList<>();
			visited = new boolean[R][C];
			q.add(new Pos(i,j));
			cnt = 0;
			//0 기준 bfs 탐색
			while(!q.isEmpty()) {
				Pos now = q.poll();
				for (int k = 0; k < 4; k++) {
					int ny = now.y + dy[k];
					int nx = now.x + dx[k];
					if(ny >= R || ny < 0 || nx >= C || nx < 0) continue;
					
					if(map[ny][nx] == 0 && !visited[ny][nx]) {
						visited[ny][nx] = true;
						q.add(new Pos(ny,nx));
					}
					if(map[ny][nx] == 1 && !visited[ny][nx]) {
						visited[ny][nx] = true;
						Integer[] temp = {ny,nx};
						deletePos.add(temp); // 경계값 치즈들 -> 0으로 바꿔줘야 할 좌표값들
						cnt++;
					}
					
				}
			}
			//경계 치즈 녹여주기
			for (int k = 0; k < deletePos.size(); k++) {
				int y = deletePos.get(k)[0];
				int x = deletePos.get(k)[1];
				map[y][x] = 0;
			}
			time++;
			Integer[] temp = {time,cnt};
			area.add(temp);
			if(cnt == 0) break;
		}
		
		

	}

}