[백준_2638번] 치즈

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

2638번: 치즈

[문제]

 N×M (5≤N, M≤100)의 모눈종이 위에 아주 얇은 치즈가 <그림 1>과 같이 표시되어 있다. 단, N 은 세로 격자의 수이고, M 은 가로 격자의 수이다. 이 치즈는 냉동 보관을 해야만 하는데 실내온도에 내어놓으면 공기와 접촉하여 천천히 녹는다. 그런데 이러한 모눈종이 모양의 치즈에서 각 치즈 격자(작 은 정사각형 모양)의 4변 중에서 적어도 2변 이상이 실내온도의 공기와 접촉한 것은 정확히 한시간만에 녹아 없어져 버린다. 따라서 아래 <그림 1> 모양과 같은 치즈(회색으로 표시된 부분)라면 C로 표시된 모든 치즈 격자는 한 시간 후에 사라진다.

 

<그림 1>

 <그림 2>와 같이 치즈 내부에 있는 공간은 치즈 외부 공기와 접촉하지 않는 것으로 가정한다. 그러므 로 이 공간에 접촉한 치즈 격자는 녹지 않고 C로 표시된 치즈 격자만 사라진다. 그러나 한 시간 후, 이 공간으로 외부공기가 유입되면 <그림 3>에서와 같이 C로 표시된 치즈 격자들이 사라지게 된다.

 

<그림 2>

<그림 3>

 모눈종이의 맨 가장자리에는 치즈가 놓이지 않는 것으로 가정한다. 입력으로 주어진 치즈가 모두 녹아 없어지는데 걸리는 정확한 시간을 구하는 프로그램을 작성하시오.

 

[입력 조건]

 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표시된다. 또한, 각 0과 1은 하나의 공백으로 분리되어 있다.

 

[코드]

import java.util.*;

class Point_2638 {
	int x,y;
	
	public Point_2638(int x, int y) {
		this.x=x;
		this.y=y;
	}
}

public class BaekJoon_2638 {
	static int[][] map;
	static boolean[][] visited;
	static int[] dx= {-1,0,1,0};
	static int[] dy= {0,-1,0,1};
	static int n,m,time=0,totalcheese=0;
	static ArrayList<Point_2638> cheese=new ArrayList<>();
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		m=sc.nextInt();
		
		map=new int[n][m];
		
		for(int i=0;i<n;i++) {
			for(int j=0;j<m;j++) {
				map[i][j]=sc.nextInt();
				
				if(map[i][j]==1) {
					totalcheese++; // 전체 치즈의 수 count
					cheese.add(new Point_2638(i,j)); // 초기의 치즈 정보 연결리스트에 저장
				}
			}
		}
		
		// 치즈의 수가 0개가 될때까지 시간 측정
		while(totalcheese!=0) {
			time++;
			visited=new boolean[n][m];
			outside_air(); // 외부공기 표시
			melting_cheese(); // 치즈 녹이기
		}
		
		System.out.println(time);
	}
	
	// 치즈 녹이는 함수
	static void melting_cheese() {
		for(int i=0;i<cheese.size();i++) {
			Point_2638 p=cheese.get(i);
			int count=0;
			
			// 상,하,좌,우에 외부공기가 있는지 탐색
			for(int d=0;d<4;d++) {
				int nx=p.x+dx[d];
				int ny=p.y+dy[d];
				
				if(nx<0||ny<0||nx>=n||ny>=m) continue; // 범위 초과
				
				if(map[nx][ny]==2)
					count++; // 외부공기 count
			}
			
			if(count>=2) { // 치즈 주변에 외부공기와 맞닿아 있는 변이 2개 이상이라면
				map[p.x][p.y]=0; // 치즈 없애기
				totalcheese--; 
				cheese.remove(i);
				i--; // 연결리스트에서 해당 치즈를 삭제하면 i를 하나 감소시켜야 빠짐없이 검사 가능(밀리지 않게)
			}
		}
	}
	
	/*
	 * 외부공기인지 체크하는 함수
	 * 가장자리인 (0,0) 부터 외부공기인지 체크를 시작하다 치즈가 있는 곳은 큐에 삽입하지 않게되면
	 * 치즈를 기준으로 상,하,좌,우는 탐색하지 않게된다. 이에 따라 치즈 내부는 자연스럽게 탐색하지 않게 되면서
	 * 치즈의 내부에 있는 공기는 고려대상이 되지 않는다. 
	 * 해당 과정을 거치면 최종적으로 치즈 외부에 있는 공기만 큐에 삽입되게 된다. 
	 */
	static void outside_air() {
		Queue<Point_2638> q=new LinkedList<>(); // 큐에는 외부공기의 위치가 저장된다.
		q.offer(new Point_2638(0,0));
		visited[0][0]=true; // (0,0)은 치즈가 반드시 없기 때문에 해당 위치에서 시작
		map[0][0]=2; // 외부공기는 2로 표시
		
		while(!q.isEmpty()) {
			Point_2638 p=q.poll();
			
			// 상,하,좌,우 탐색
			for(int i=0;i<4;i++) {
				int nx=p.x+dx[i];
				int ny=p.y+dy[i];
				
				if(nx<0||ny<0||nx>=n||ny>=m) continue; // 범위 초과
				
				// 이미 방문했거나 치즈인 경우도 넘어간다.
				if(visited[nx][ny]||map[nx][ny]==1) continue; 
				
				map[nx][ny]=2; // 외부공기 표시
				visited[nx][ny]=true;
				q.offer(new Point_2638(nx,ny));
			}
		}
	}
}

 

[고찰]

 이번 문제는 이전에 풀었던 백준 2636번 치즈 문제와 유사했다. 2636번은 치즈와 외부 공기가 한 면만 맞닿아 있어도 치즈를 없애야하기 때문에 좀 더 쉽게 해결할 수 있었지만 이번 문제는 치즈와 외부 공기가 두 면 이상 맞닿아 있어야 치즈를 없애야했다. 따라서 치즈의 외부 공기를 따로 구해주어야 하는 과정이 필요했다. 

 

*** 1) 외부 공기 체크(outside_air 함수)

 문제에는 가장자리에는 치즈가 올 수 없다고 적혀있기 때문에 (0,0)은 반드시 외부 공기가 된다. (0,0) 부터 외부공기인지 체크를 시작하다가 치즈를 만나게 되면 해당 좌표는 큐에 삽입하지 않는 방법으로 치즈 내부 공기와 외부 공기를 구별할 수 있다. 

치즈가 있는 곳은 큐에 삽입하지 않게되면 치즈를 기준으로 상,하,좌,우는 탐색하지 않게된다. 이에 따라 치즈 내부는 자연스럽게 탐색하지 않게 되면서 치즈의 내부에 있는 공기는 고려대상이 되지 않는다. 해당 과정을 거치면 최종적으로 치즈 외부에 있는 공기만 큐에 삽입되게 되기 때문에 외부 공기의 좌표 값을 2로 바꿔주어 구별한다.

 

*** 2) 치즈 녹이기(melting_cheese 함수)

 외부 공기와 내부 공기를 구별했다면 초기 치즈를 모두 탐색하면서 치즈 주변에 외부 공기가 있는 칸을 count 해주면 된다. count 한 값이 2 이상이라면 없어져야 하는 치즈이기 때문에 연결리스트에서 제거해주면 된다. 

 

 이번 문제는 치즈를 기준으로 외부 공기와 내부 공기를 구별해주는 코드는 어렵지 않았지만 이유를 이해하는 것이 까다로웠던것 같다.