[BOJ 2636] 치즈 (Java)

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

2636번: 치즈

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

public class Main_BOJ_2636 {
	static int[] dr= {-1,1,0,0};
	static int[] dc= {0,0,-1,1};
	static int N, M;
	static int[][] map;
	static int cheese=0;
	static ArrayList<Integer> li=new ArrayList<>();
	public static void main(String[] args) throws IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer(br.readLine());
		N=Integer.parseInt(st.nextToken());
		M=Integer.parseInt(st.nextToken());
		map=new int[N][M];
		for (int i=0; i<N; i++) {
			st=new StringTokenizer(br.readLine());
			for (int j=0; j<M; j++) {
				map[i][j]=Integer.parseInt(st.nextToken());
				if (map[i][j]==1) cheese++;
			}
		}
		int count=0;
		airCheck(0,0);
		while(true) {
			ArrayList<int[]> melted=new ArrayList<>();
			li.add(cheese);
			if (cheese==0) {
				break;
			}
			for (int i=0; i<N; i++) {
				for (int j=0; j<M; j++) {
					if (map[i][j]==1) {		//녹을 치즈 선정
						if (cheeseCheck(i,j)) {
							cheese--;
							melted.add(new int[] {i,j});
						}
					}
				}
			}
			for (int[] cheese : melted) {		//녹을 치즈 중 공기 업데이트
				if (map[cheese[0]][cheese[1]]==1) {
					airCheck(cheese[0], cheese[1]);
				}
			}
			count++;
		}
		System.out.println(count+"\n"+li.get(li.size()-2));
	}
	private static boolean cheeseCheck(int r, int c) {
		for (int i=0; i<4; i++) {
			int nr=r+dr[i];
			int nc=c+dc[i];
			if (nr<0 || nc<0 || nr>=N || nc>=M) continue;
			if (map[nr][nc]==-1) return true;
		}
		return false;
		
	}
	private static void airCheck(int y, int x) {
		Queue<int[]> q=new LinkedList<>();
		q.add(new int[] {y,x});
		map[y][x]=-1;
		while (!q.isEmpty()) {
			int[] pos=q.poll();
			int r=pos[0];
			int c=pos[1];
			for (int i=0; i<4; i++) {
				int nr=r+dr[i];
				int nc=c+dc[i];
				if (nr<0 || nc<0 || nr>=N || nc>=M) continue;
				if (map[nr][nc]==0) {
					map[nr][nc]=-1;
					q.add(new int[] {nr,nc});
				}
			}
		}
	}
}

1. 우선 반복문을 돌기 전에 (0,0) 부터 bfs를 돌려줘서 바깥 공기를 찾는다.

2. 반복문을 돈다.

   1) 치즈의 갯수를 체크해서 0이면 반복문 탈출

   2) map을 돌면서 1인 것에 대해(치즈) 바깥 공기와 접촉하는지 체크한 후 접촉한다면 치즈의 갯수를 줄여주고 녹을 치즈 리스트에 넣어준다.

   3) 녹을 치즈 리스트에 속한 애들을 BFS 돌리면서 바깥 공기를 업데이트한다..

 

 

좀 복잡하게 푼 것 같다.

다른 분의 코드(https://ongveloper.tistory.com/159?category=854013) 를 보니,

 치즈가 없을 때까지 BFS를 (0,0)번부터 쭉 돌리는 작업을 반복한다. 이때 주의할 점은 0을 만나면 계속 탐색하고 1을 만나면 0으로 바꿔주기만 하고 탐색 대상에 넣지 않는 것이다.