백준 2636번 : 치즈

 문제

www.acmicpc.net/problem/2636

2636번: 치즈

2636 치즈

 

 구현 방법

 단계적으로 생각해보았습니다.

1. 치즈 겉 공기 구하기 - (0, 0)은 무조건 빈 칸, (0, 0)부터 인접한 곳이 빈 칸일 때 bfs 돌려 check 배열에 1로 저장. 치즈 속 공기는 1로 둘러쌓여 있기 때문에  치즈 속 공기까지 도달하지 못함.

2. 치즈 속 공기 구하기 - check 배열 값이 0이고 cheese 배열 값이 0이면 치즈 속 공기 -> 2로 변경

3. 사라질 치즈 구하기 - cheese 배열을 탐색하여 배열 값이 1 즉, 치즈일 때 인접한 배열 값을 확인하여 빈 칸이라면 check 

4. 치즈 없애기 - check에 해당하는 값 0으로 바꿔주기

5. 치즈 속 빈 공간 초기화

6. 치즈가 전부 사라질 때까지 반복

 

 구현 코드

package baekjoon.gold;

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

public class BOJ2636_치즈 {
	static int R, C, ans, tmp, cnt;
	static int[][] cheese, check, deltas = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
	static Queue<int[]> bfs;
	static boolean flag;
	public static void main(String[] args) throws 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());
		cheese = new int[R][C];
		for (int r=0;r<R;r++) {
			st = new StringTokenizer(br.readLine());
			for (int c=0;c<C;c++) {
				cheese[r][c] = Integer.parseInt(st.nextToken());
			}
		}
        // 입력완료
		bfs = new LinkedList<>();
		while(true) {
			flag = false;
			// 공기 탐색
			check = new int[R][C];
			bfs.offer(new int[] {0, 0});
			check[0][0] = 1;
			bfsL();
			
            for (int r=0;r<R;r++) {
				for (int c=0;c<C;c++) {
					if (check[r][c]==0 && cheese[r][c]==0) cheese[r][c]=2; // 치즈 속 공기는 2
				}
			}
            
			// 사라질 치즈 탐색
			tmp = 0; // 치즈 개수 카운팅 초기화
			check = new int[R][C];
			for (int r=1;r<R-1;r++) {
				for (int c=1;c<C-1;c++) {
					if (cheese[r][c]==1) {
						flag = true; // 치즈 있다!!
						tmp++;
						stop:for (int d=0;d<4;d++) {
							int nr = r+deltas[d][0];
							int nc = c+deltas[d][1];
							if (cheese[nr][nc]==0) {
								check[r][c]=1; 
								break stop;
							}
						}
					}
				}
			}
			
			if (!flag) break; // 치즈가 없으면 끝내주기
			
			// 치즈 제거
			for (int r=1;r<R-1;r++) {
				for (int c=1;c<C-1;c++) {
					if (check[r][c]==1 || cheese[r][c]==2) cheese[r][c] = 0; // 치즈 없애주기, 치즈 속 빈공간 초기화
				}
			}
			
			cnt = tmp; // 치즈 개수 저장
			ans++;
		}
		
		System.out.println(ans+"\n"+cnt);
	}
	
	static void bfsL() {
		while(!bfs.isEmpty()) {
			int size = bfs.size();
			for (int i=0;i<size;i++) {
				int[] now = bfs.poll();
				for (int d=0;d<4;d++) {
					int nr = now[0]+deltas[d][0];
					int nc = now[1]+deltas[d][1];
					if (isIn(nr, nc) && cheese[nr][nc]==0 && check[nr][nc]==0) {
						check[nr][nc] = 1;
						bfs.offer(new int[] {nr, nc});
					}
				}
			}
		}
	}
	
	static boolean isIn(int nr, int nc) {
		return nr>=0 && nr<R && nc>=0 && nc<C;
	}
}

 

정답!