[JAVA] 백준 2636번: 치즈

🔗 문제

2636번: 치즈

2636번: 치즈

• N, M ≤ 100

아래 <그림 1>과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(<그림 1>에서 네모 칸에 X친 부분)에는 치즈가 놓여 있지 않으며 치즈에는 하나 이상의 구멍이 있을 수 있다.

이 치즈를 공기 중에 놓으면 녹게 되는데 공기와 접촉된 칸은 한 시간이 지나면 녹아 없어진다. 치즈의 구멍 속에는 공기가 없지만 구멍을 둘러싼 치즈가 녹아서 구멍이 열리면 구멍 속으로 공기가 들어가게 된다. <그림 1>의 경우, 치즈의 구멍을 둘러싼 치즈는 녹지 않고 ‘c’로 표시된 부분만 한 시간 후에 녹아 없어져서 <그림 2>와 같이 된다.

 

✏️ 풀이

치즈의 가장 자리 녹이기에서 해야할 일은 구체적으로 3가지다.

1. 치즈 가장 자리 찾기
2. 치즈 가장 자리 녹이기
3. 남은 치즈 개수 세기

하나씩 뜯어보자.

 

🧀 치즈 가장 자리 찾기 & 치즈 가장 자리 녹이기

문제에 힌트가 있다.

판의 가장자리(<그림 1>에서 네모 칸에 X친 부분)에는 치즈가 놓여 있지 않으며

 

 

BFS로 판의 가장 자리 아무거나 골라서 BFS하면 된다.

 

BFS(0,0)

: 빈 공간을 사방 탐색한다.

• 치즈를 만난다면 ? 녹인다.
• 빈 공간을 만난다면? queue에 녹인다.

 

 

치즈를 탐색하며 제거해버리면 잘못 계산하지 않나? 라는 생각이 들 수도 있는데, 로직에서 재방문처리를 visited로 관리하며 방지할 수 있다.

→ 자연스럽게 원하던 기능1과 기능2가 한번에 해결되었다.

 

🧀 남은 치즈 개수 세기

종료 조건은 ‘남은 치즈 칸‘ 가 0일 때인데 결과값은 ‘직전의 남은 치즈 칸’다.

그렇다는 말은 직전 치즈 개수를 저장해 놓으라는 말이다.

chesse // 총 치즈 개수. 입력 받을 때 증가, 치즈 녹을 때 마다 감소
cnt //  BFS 직전의 cheese값 저장

---

 

➕ 조금 시간 줄이는 방법

bfs()를 돌릴 때 계속 (0, 0)부터 돌리는 것이 아닌 직전에 녹였던 치즈 위치부터 시작하면 조금이나마 시간을 줄일 수 있다 ❤️

 

💾  소스

import java.io.*;
import java.util.*;

public class Main {
	
	static BufferedReader br;
	static StringTokenizer st;
	static int N, M, answer=0, cnt = 0, cheese = 0;
	static int[] dx = {0, 0, 1, -1};
	static int[] dy = {1, -1, 0, 0};
	static boolean map[][];

	static boolean isValid(final int x, final int y)
	{
		if(x<0 || y<0 || x>=N || y>=M)
			return false;
		return true;
	}
	
	static class Pair
	{
		int x, y;

		public Pair(final int x, final int y) {
			super();
			this.x = x;
			this.y = y;
		}
	};
	
	
	static boolean solve()
	{
		++answer;

		Queue<Pair> air = new ArrayDeque<>();
		boolean[][] visited = new boolean[N][M];

		air.add(new Pair(0, 0));
		visited[0][0] = true;
		
		Pair top;
		cnt = cheese;
		
		while(!air.isEmpty())
		{
			top = air.poll();
			visited[top.x][top.y] = true;
			
			for(int d=0; d<4; ++d)
			{
				int x = top.x + dx[d];
				int y = top.y + dy[d];
				
				if(!isValid(x, y)|| visited[x][y])
					continue;
				
				if(map[x][y])
				{
					map[x][y] = false;
					--cheese;
				}				
				else
				{
					air.add(new Pair(x, y));
				}
				
				visited[x][y] = true;
			}
		}
		
		return cheese <= 0 ? true : false;
	}
	
	public static void main(String[] args) throws IOException {
				
		br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		map = new boolean[N+1][M+1];		
		
		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()) == 0 ? false : true;
				if(map[i][j]) ++cheese;
			}
		}
		
		
		while(true)
		{
			if(solve()) break;
		}
		
		sb.append(answer).append("\\n").append(cnt);
		System.out.print(sb);

	} // main
}