[BJ] 2636. 치즈

www.acmicpc.net/problem/2636

2636번: 치즈

 

✔ 문제 조건

1. map: 치즈 or 빈칸
   • 0: 빈칸, 1: 치즈가 있는 칸
2. 치즈
   • 공기와 접촉 시 한시간 후 녹아 없어짐
3. 빈칸
   • 치즈 밖에 있는 빈칸은 공기로, 치즈 덩어리의 가장자리와 닿으면 닿은 치즈 칸은 녹는다.
   • 치즈 안에 있는 빈칸은 구멍으로 공기가 아니다. 치즈가 녹으면서 구멍이 열리면 공기가 들어가 치즈를 녹이게 된다.
4. 치즈가 모두 녹아 없어지는데 걸리는 시간과, 녹기 한 시간 전에 남아있는 치즈 칸의 개수 출력

 

✔ 접근 과정

1. 반복문을 시작하기 전마다 마지막으로 남은 치즈 개수를 기록한다.
2. 공기부터 bfs를 시작하며 만나게 되는 치즈를 녹인다.
3. 치즈 개수가 0이되면 종료하고, 0이 아니라면 반복문을 계속 돈다.

 

✔ 주의할 점

1. 0을 만났을 때 바깥 공기인지 안쪽 구멍인지 어떻게 구분하나 싶었는데. bfs를 돌 때 공기 칸 (0, 0)에서 시작해서 만나는 칸들은 모두 공기이다.
2. 공기가 치즈를 만나는지를 찾아야 하니까. 공기를 만날 때 마다 방문 처리 후 큐에 넣고 치즈를 만나면 녹인다.

 

import java.io.*;
import java.util.*;
// 210422

public class Main_BJ_2636_치즈 {
	static int H, W, cheeseCnt; // 세로, 가로
	static int[][] map; // 0: 빈칸, 1: 치즈
	static int[] dr = {-1, 0, 1, 0};
	static int[] dc = {0, -1, 0, 1};
	
	static class Pos{
		int r, c;

		public Pos(int r, int c) {
			this.r = r;
			this.c = c;
		}
	}
	
	public static void main(String[] args) throws Exception {
		//System.setIn(new FileInputStream("res/input_BJ_2636_치즈.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		H = stoi(st.nextToken());
		W = stoi(st.nextToken());
		map = new int[H][W];
		cheeseCnt = 0;
		
		for(int i=0; i<H; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for(int j=0; j<W; j++) {
				map[i][j] = stoi(st.nextToken());
				if(map[i][j]==1) ++cheeseCnt;
			}
		}
		
		solve();
		br.close();
	}
	
	static void solve() {
		int lastCnt = 0;
		int time = 0;
		
		while(true) {
			lastCnt = cheeseCnt;
			++time;
			bfs();
			if(cheeseCnt==0) break;
		}
		
		System.out.println(time);
		System.out.println(lastCnt);
	}
	
	static void bfs(){
		// 공기를 만날 때 마다 녹여야 하기 때문에, 공기 칸인 0, 0에서 시작
		// 공기 칸에서 시작하며 만나는 빈칸은 구멍이 아니라 공기다.
		
		boolean[][] v = new boolean[H][W];
		ArrayDeque<Pos> q = new ArrayDeque<>();
		v[0][0] = true;
		q.offer(new Pos(0, 0));
		
		while(!q.isEmpty()) {
			Pos cur = q.poll();
		
			for(int d=0; d<4; d++) {
				int nr = cur.r + dr[d];
				int nc = cur.c + dc[d];
				
				if(nr<0 || nr>=H || nc<0 || nc>=W || v[nr][nc]) continue;
				if(map[nr][nc]==0) { // 만나게 되는 공기는 다음 탐색 지점
					v[nr][nc] = true;
					q.offer(new Pos(nr, nc));
					
				} else if(map[nr][nc]==1) { // 치즈를 만나면
					v[nr][nc] = true;
					map[nr][nc] = 0;
					--cheeseCnt;
				}
			}

		}

	}
	
	static int stoi(String str) {
		return Integer.parseInt(str);
	}
}

 

✔첫번째 시도

1. 치즈의 위치를 큐에 넣어두고, 치즈 개수도 cheeseCnt로 따로 센다.
2. for문으로, 치즈 하나씩 4방탐색 시키며 공기를 만나면
   • 배열에 치즈 위치를 넣어두고
3. for문이 끝날 때 마다 list속 치즈 위치를 0으로 만들고 (치즈를 녹이고), cheeseCnt--
4. cheeseCnt>0이라면 (치즈가 아직 남아있다면) 2로 돌아간다.

 

• for문을 돌며 치즈가 공기와 만날 때 마다 바로 녹이면, 그 위치를 다음 치즈가 공기로 인식해서 1번 만에 모든 치즈가 녹아버린다.
• 따라서 list에 치즈 위치만 넣어두고 한꺼번에 녹인다.

 

🧨 문제는, 치즈 안쪽 빈칸도 공기로 인식해버림
-> 치즈를 경계로 바깥과 안을 구분해야 함

 

 

✔두번째 시도

1. 치즈의 개수만 cheeseCnt로 세둔다.
2. bfs
   • (0, 0) 처음 공기 위치에서 시작하여 (q <- (0, 0) ) & 방문처리
   • 큐에서 하나씩 꺼내며
     1) 공기를 만나면 -> q <- (nr, nc) & 방문처리2) 치즈를 만나면 -> 녹이고 ( map[nr][nc]=0) && cheeseCnt--
3. cheeseCnt>0이라면 (치즈가 아직 남아있다면) 2로 돌아간다.

 

🧨 또 문제,,,,,,
q.offer(nr, nc) & 방문 처리를 한쌍으로 생각해왔다.
공기를 만날 때만 방문 처리를 해버리면,
치즈를 만나서 녹였을 때, 그 위치를 다음 공기의 nr, nc에서 빈칸으로 인식해서 q에 넣어버린다.
따라서, 치즈를 만나서 녹였을 때도 방문 처리를 해서 빈칸으로 인식 못하게 해야 한다.

즉, 공기를 만나든 치즈를 만나든 매번 방문 처리를 해야 한다.

 

 

✔세번째 시도

1. 치즈의 개수만 cheeseCnt로 세둔다.
2. bfs
   • (0, 0) 처음 공기 위치에서 시작하여 (q <- (0, 0) ) & 방문처리
   • 큐에서 하나씩 꺼내며
     • 1) 공기를 만나면 -> q <- (nr, nc) & 방문처리
     • 2) 치즈를 만나면 -> 녹이고 ( map[nr][nc]=0) && cheeseCnt-- && 방문처리
3. cheeseCnt>0이라면 (치즈가 아직 남아있다면) 2로 돌아간다.