BOJ. 2638번. 치즈

 

어디서 이렇게 비슷하게 생긴 문제들이 계속 나타나는지 모르겠다ㅎㅎ

단순한 BFS문제다. 다만 내부에 공기층이 생긴 경우 이를 따로 처리해 주어야 한다. 나는 거꿀로 외부에서부터 BFS탐색을 돌면서 외부 공기층을 2로 바꾸고, 이 외부 공기층( 2 )와 2면 이상 인접한 치즈들을 녹여주었다. 

www.acmicpc.net/problem/2638

2638번: 치즈

package week9;

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

public class Day5BOJ2638 {

	static int n,m,time;
	static int[][] map;
	static boolean[][] c;
	static int[] dy = {1,-1,0,0};
	static int[] dx = {0,0,-1,1};
	static class Pos{
		int y,x;
		public Pos(int y, int x) {
			this.y = y;
			this.x = x;
		}
	}
    
	static Queue<Pos> targets = new LinkedList<Pos>(); 
	
	private static boolean checkBound(int y, int x) {
		return (y>=0&&y<n&&x>=0&&x<m) ? true : false;
	}
	
	private static void changeOuterAir(int y, int x) {
		c= new boolean[n][m];
		Queue<Pos> outer = new LinkedList<Pos>();
		outer.offer(new Pos(y,x));
		c[y][x] = true;
		
		while(!outer.isEmpty()) {
			Pos cur = outer.poll();
			for(int d=0; d<4; d++) {
				int ny=cur.y+dy[d];
				int nx=cur.x+dx[d];
				if(checkBound(ny,nx)&&!c[ny][nx]&&(map[ny][nx]==0||map[ny][nx]==2)) {
					map[ny][nx]=2;
					c[ny][nx]=true;
					outer.offer(new Pos(ny,nx));
				}
			}
		}
		
	}
	
	private static boolean checkIfFinished() {
		boolean flag = true;
		for(int i=0; i<n; i++) {
			for(int j=0; j<m; j++) {
				if(map[i][j]==1) {
					flag=false;
					break;
				}
			}
		}
		return flag;
	}
	private static boolean checkIfMelt(int y, int x) {
		int cnt=0;
		for(int d=0; d<4; d++) {
			int ny = y+dy[d];
			int nx = x+dx[d];
			if(checkBound(ny,nx) && map[ny][nx]==2) {
				cnt++;
			}
		}
		return (cnt>=2) ? true : false; 
	}
	
	private static void solution() {
		while(true) {
			// 외부 공기 2로 변환
			changeOuterAir(0,0);
			
			// 녹일지점 선택
			for(int i=0; i<n; i++) {
				for(int j=0; j<m; j++) {
					if(map[i][j]==1 && checkIfMelt(i,j)) {
						targets.offer(new Pos(i,j));
					}
				}
			}
            
			// 녹인다
			for(Pos t : targets) {
				map[t.y][t.x] = 0;
			}
			targets.clear();
			time++;

			// 확인
			if(checkIfFinished()) break;
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		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());
			}
		}
		
		solution();
	
		System.out.println(time);
	}

}