[알고리즘] Java / 백준 / 치즈 / 2638

[알고리즘] Java / 백준 / 치즈 / 2638

문제

문제 링크

접근 방식

바깥 테두리는 무조건 공기이므로 0,0 좌표로부터 치즈가 아닌곳이 외부 공기이다.

외부공기와 2변 이상 접촉한 치즈만 1시간 후에 사라진다.

1. 0,0 좌표에서 치즈가 아닌 곳을 bfs 탐색한다.
2. 외부와 접촉한 수를 저장할 temp[][] 를 만들고, 치즈를 만나면(외부 공기와 치즈가 접촉하면) 해당 좌표에 1을 더한다(temp[i][j]++)
3. bfs 탐색이 끝나고 temp를 확인하여 외부와 접촉한 수가 2 이상일 경우 치즈를 없앤다.
4. 치즈의 개수를 세고 0이 아니면 시간을 올리고 1번부터 다시 반복한다.

코드

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

public class Main_2638 {

	static int N,M;
	static int[][] cheezes;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		cheezes = new int[N][M];
		
		for(int i=0;i<N;i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0;j<M;j++) {
				cheezes[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		System.out.println(go());
		
		
		
	}
	
	public static int go() {
		
		int t = 0;
		
		while(cheezeCnt()!=0) {
			int[][] contactAir = bfs();
			meltCheeze(contactAir);
			t++;
		}
		
		return t;
	}
	
	public static void meltCheeze(int[][] contactAir) {
		for(int i=0;i<N;i++) {
			for(int j=0;j<M;j++) {
				if(contactAir[i][j] >= 2)
					cheezes[i][j] = 0;
			}
		}
	}
	
	public static int cheezeCnt() {
		int cnt = 0;
		
		for(int i=0;i<N;i++) {
			for(int j=0;j<M;j++) {
				if(cheezes[i][j] == 1)
					cnt++;
			}
		}
		
		return cnt;
	}
	
	public static class Node{
		int r;
		int c;
		
		Node(int r, int c){
			this.r = r;
			this.c = c;
			
		}
	}
	
	static int[] dr = {0,1,0,-1};
	static int[] dc = {1,0,-1,0};
	public static int[][] bfs() {
		
		// 치즈가 외부와 접촉한 변의 개수
		int[][] temp = new int[N][M];
		
		Queue<Node> q = new LinkedList<>();
		q.add(new Node(0,0));
		
		boolean[][] visited = new boolean[N][M];
		visited[0][0] = true;
		
		while(!q.isEmpty()) {
			Node node = q.poll();
			
			for(int i=0;i<4;i++) {
				int nr = node.r + dr[i];
				int nc = node.c + dc[i];
				
				if(nr<0 || nr>=N || nc<0 || nc>=M || visited[nr][nc]) continue;
				
				// 다음 위치가 치즈이면
				if(cheezes[nr][nc] == 1) 
					temp[nr][nc]++;
				else {
					visited[nr][nc] = true;
					q.add(new Node(nr,nc));
				}
			}
		}
		
		return temp;
	}

}