[BOJ 2638] 치즈 (Java)

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

2638번: 치즈

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_2638 {
	static int N, M;
	static int[][] map;
	static boolean[][] isAir;
	static int air;
	static int answer=0;
	static ArrayList<int[]> li=new ArrayList<>();
	static int[] dr= {-1,1,0,0};
	static int[] dc= {0,0,-1,1};
	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];
		isAir=new boolean[N][M];
		li.add(new int[] {0,0}); 
		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());
			}
		}
		while (true) {
			check();
			if (air==N*M) break;
			li.clear();
			melt();
			answer++;
		}
		System.out.println(answer);

	}
	private static void check() {			//외부 공기 표시하기
		Queue<int[]> q=new LinkedList<>();
		for (int[] arr : li) {
			q.add(arr);
			isAir[arr[0]][arr[1]]=true;
			air++;
		}
		while (!q.isEmpty()) {
			int[] pos=q.poll();
			for (int i=0; i<4; i++) {
				int nr=pos[0]+dr[i];
				int nc=pos[1]+dc[i];
				if (nr<0 || nc<0 || nr>=N || nc>=M) continue;
				if (map[nr][nc]==0 && !isAir[nr][nc]) {
					isAir[nr][nc]=true;
					air++;
					q.add(new int[] {nr,nc});
				}
			}
		}
	}
	
	private static void melt() {
		for (int i = 0; i < N; i++) {
			for (int j=0; j<M; j++) {
				if (map[i][j]==0) continue;
				int cnt=0;
				for (int d=0; d<4; d++) {
					int nr=i+dr[d];
					int nc=j+dc[d];
					if (isAir[nr][nc]) cnt++;
				}
				if (cnt>=2) {
					li.add(new int[] {i,j});
				}
			}
		}
		for (int[] arr : li) {
			map[arr[0]][arr[1]]=0;
		}
		
	}

}

프로세스는 다음과 같다.

 

1. 외부 공기 갱신하기

2. 외부 공기가 N*M개(즉 치즈가 0개)면 해당 프로세스를 종료

3. 치즈 리스트 비운 후, 갱신된 외부 공기에 대해 녹을 치즈를 치즈 리스트에 넣은 후, 녹인다(map에 0 표시)

 

외부 공기 갱신은 check() 함수로,

이전에 녹은 치즈 (첫번째 호출 때는 (0,0)) 의 좌표들을 큐에 넣어주고, BFS 탐색을 진행하면서

map이 0이고 isAir가 false(즉 미방문)인 위치에 대해 모두 방문해준다.

 

melt() 함수에서는, map을 모두 돌면서 치즈인 위치에 대해, 주변 4방향을 모두 탐색하면서 그 중 외부 공기로 표시된 것이 2개 이상이면 녹을 치즈 리스트에 넣어준다. 

 

다른분의 코드(https://yabmoons.tistory.com/342) 를 보니

녹일 치즈를 선정할 때 map의 원소를 모두 탐색하는 것이 아니라 입력받을 때 치즈의 위치를 리스트에 따로 저장한다.

그 치즈 리스트를 순회하면서 이미 녹인 치즈일 경우 제외하고, 아직 녹지 않은 치즈면 탐색을 진행해서 외부공기와 닿는 면이 얼마나 있는지 체크한다. 이 코드 역시, 녹인 치즈를 큐에 넣어서 외부 공기를 표시해 주었다.