[백준] 2638번:치즈 (Java 자바)

문제

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

2638번: 치즈

 

풀이 및 소스코드

 

간단한 DFS/BFS 문제인 줄 알았으나,

바깥공기와 내부공기(?) 를 나눠야 하는 것에서 조금 멈칫했다.

문제를 보면

모눈종이의 맨 가장자리에는 치즈가 놓이지 않는 것으로 가정한다.

라는 문장이 있다. !

모눈종이의 맨 가장자리는 치즈가 놓이지 않는 즉, 바깥 공기가 존재하는 곳이다.

따라서 녹을 치즈를 찾기 전, 모눈종이의 맨 가장자리와 연결되어 있는 곳들의 값들을 -1로 바꿔준다.

그렇게 되면,

-1 인 곳 : 바깥 공기가 존재하는 곳

0인 곳 : 안쪽 공기가 존재하는 곳

으로 나뉠 수 있다.

위의 설명을 그림으로!!

그 다음부터는

값이 1인 곳들을 찾아 상하좌우 중 -1인 곳에 대해 카운트를 진행한다.

-1 인 곳이 주변에 두개 이상 존재한다면 (cnt>=2)

 

 

단, 치즈가 한 번 녹을 때 마다 바깥 공기 부분과 안쪽 공기 부분은 바뀔 수 있으므로 한 시간이 지날 때 마다 이 과정을 반복해준다.

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

class Main {
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int[][] 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());
			}
		}
		int res = 0;
		int[] dx = {-1, 1, 0, 0};
		int[] dy = {0, 0, -1, 1};
		while(true) {
			Queue<Integer[]> q = new LinkedList<>();
			q.add(new Integer[]{0,0});
			map[0][0]=-1;
			while(!q.isEmpty()) {
				//바깥공기 영역 구하기 !!
                //bfs 사용
				Integer[] tmp = q.poll();
				int x = tmp[0];
				int y = tmp[1];
				for(int i=0;i<4;i++) {
					int nowx = x+dx[i];
					int nowy = y+dy[i];
					if(nowx<0||nowy<0||nowx>=n||nowy>=m) {
						continue;
					}
					if(map[nowx][nowy]==0) {
						map[nowx][nowy]=-1;
						q.add(new Integer[] {nowx,nowy});
					}
				}
			}
			Queue<Integer> xx = new LinkedList<>();
			Queue<Integer> yy = new LinkedList<>();
			for(int i=0;i<n;i++) {
				for(int j=0;j<m;j++) {
					int cnt = 0;
					if(map[i][j]==1) {
						for(int d=0;d<4;d++) {
							int nowx = i+dx[d];
							int nowy = j+dy[d];
							if(nowx<0||nowy<0||nowx>=n||nowy>=m) {
								continue;
							}
							//범위 나가버리면 컨티뉴
							
							if(map[nowx][nowy]==-1) {
								cnt ++;
								if(cnt>=2) break;
								//두개이상이 비었다면 더이상 볼 필요 없으니 break
							}
						}
						if(cnt>=2) {
							xx.add(i);
							yy.add(j);
							//없어질 치즈 좌표를 넣어준다.
						}
					}
				}
			}
			if(xx.isEmpty()) {
				System.out.println(res);
				System.exit(0);
			}
			//사라질 치즈 후보가 없다는 것은 치즈가 모두 녹아서 없어졌다는 것.
			//res를 출력해주고 종료해주자.
			
			//종료가 되지 않았다는 것은 아직 치즈가 있다는 것.
			//없어질 치즈들을 없애주고, while문 진행
			res++;
			while(!xx.isEmpty()) {
				map[xx.poll()][yy.poll()] = 0;
			}
			for(int i = 0;i<n;i++) {
				for(int j=0;j<m;j++) {
					if(map[i][j]==-1) {
						map[i][j]=0;
					}
				}
			}
		}
	}
}