[백준] 2638 - 치즈

[문제링크]

2638번: 치즈

 

0. 내부 공기엔 인접해도 녹지 않으므로, 외곽 공기에 대해서만 bfs를 진행.

  - 0,0은 항상 밖의 공기이다

 

1. 0,0을 시작점으로, 외곽 공기를 bfs로 순회한다

  - 치즈를 처음 만나면, 표시만 한다

  - 치즈를 2번째로 만나면, 제거 대상 치즈로 판단, 저장한다

 

2. 1번에서 저장된 제거대상 치즈를 제거한다

 

3. 위 과정을 치즈가 없어질때까지 반복한다

 

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

public class Main{
	static int[] dx= {1,0,-1,0};
	static int[] dy= {0,1,0,-1};
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int n = pint(st.nextToken());
		int m = pint(st.nextToken());
		int[][]map = new int[n][m];
		int chCnt=0;
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine()," ");
			for (int j = 0; j < m; j++) {
				map[i][j]=pint(st.nextToken());
				if(map[i][j]==1)chCnt++;
			}
		}
		int time=0;
		
		Queue<int[]>qu = new LinkedList<int[]>();
		Queue<int[]>removeCh = new LinkedList<int[]>();
		
		while(chCnt!=0) {
			time++;
			//bfs돌며 제거할 치즈 탐색
			int[][]isV = new int[n][m];
			qu.offer(new int[] {0,0});
			isV[0][0]=1;
			while(!qu.isEmpty()) {
				int[] ch = qu.poll();
				
				for (int i = 0; i < 4; i++) {
					int tx = ch[0]+dx[i], ty=ch[1]+dy[i];
					if(tx<0||tx>=n||ty<0||ty>=m)continue;
					
					//미방문 공기
					if(isV[tx][ty]==0 && map[tx][ty]==0) {
						isV[tx][ty]=1;
						qu.offer(new int[] {tx,ty});
					}
					//치즈 처음 만남
					else if(isV[tx][ty]==0) {
						isV[tx][ty]=1;
					}
					//치즈 2번째 만남
					else if(isV[tx][ty]==1 && map[tx][ty]==1) {
						isV[tx][ty]=2;
						removeCh.offer(new int[] {tx,ty});
					}
					
				}
			}
			
			//녹을 치즈 제거
			chCnt-=removeCh.size();
			while(!removeCh.isEmpty()) {
				int[] ch = removeCh.poll();
				map[ch[0]][ch[1]]=0;
			}
			
		}
		
		System.out.println(time);
	}
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면