[BOJ-2636][BFS] 치즈 - Java

문제 바로가기

2636번: 치즈

 

오랜만에 BFS 문제입니다.

치즈의 구멍을 둘러싼 치즈는 녹지 않도록 하는게 관건입니다.

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

public class Main {

	static class Dir{
		int y, x;
		Dir(int y, int x){
			this.y = y; this.x = x;
		}
	}
	
	static int N, M;
	static int[][] map;
	static int remained, last;
	static int[] dy = {1, -1, 0, 0};
	static int[] dx = {0, 0, 1, -1};
	
	public static void main(String[] args) throws IOException {
		input();
		
		System.out.println(solve());
		System.out.println(last);
	}
	
	public static int solve() {
		int time = 0;
		
		while(true) {
			time++;
			
			bfs(new Dir(0, 0));
			if(remained == 0) break;
		}
		
		return time;
	}
	
	public static void bfs(Dir s) {
		Queue<Dir> q = new LinkedList<>();
		List<Dir> adj = new ArrayList<>();
		boolean[][] v = new boolean[N][M];
		
		q.offer(s);
		v[s.y][s.x] = true;
		
		while(!q.isEmpty()) {
			Dir cur = q.poll();
			
			for(int i = 0; i < 4; i++) {
				Dir next = new Dir(cur.y + dy[i], cur.x + dx[i]);
				if(!isIn(next) || v[next.y][next.x]) continue;
				
				if(map[next.y][next.x] == 0) q.offer(next);
				else if(map[next.y][next.x] == 1) adj.add(next);
				
				v[next.y][next.x] = true; 
			}
		}
		
		last = remained;
		remained -= adj.size();
		
		for(Dir c : adj) {
			map[c.y][c.x] = 0; 
		}
		
	}
	
	public static boolean isIn(Dir c) {
		if(0 <= c.y && c.y < N && 0 <= c.x && c.x < M) return true;
		else return false;
	}

	public static void input() 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());
		
		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());
				if(map[i][j] == 1) remained++;
			}
		}
		
	}
}

 

바깥하고 닿은 부분만 녹아야 하니깐 바깥에서 BFS를 돌리면 됩니다.

이 때 가장자리는 절대 치즈가 올 수 없으니깐 N*N 볼 필요 없이 (0, 0) 에서 돌려주면 됩니당.

 

BFS를 돌릴 때 치즈인 공간을 만나면 그 부분은 공기와 맞닿은 부분이겠져. 얘들의 리스트를 하나 만들어서 거기다 저장해뒀습니다.

문제에서 치즈가 모두 녹기 한 시간 전에 남은 치즈 칸의 개수도 구하라 했으니 BFS를 다 돌리고 나면 last 변수에 남아있는 애들을 저장해놓고 adj의 사이즈만큼 남은 애들을 빼주면 됩니당. 그리고 adj 리스트를 반복하면서 공기(0)으로 갱신하면 끝!!

 

 

2638보다 더 어려운듯 ;;; 허허

감사합니다!!