[JAVA] 백준 2638 : 치즈

문제

2638번: 치즈

해결 방법

하루가 지나면 녹는 치즈들이 며칠 후에 완전히 녹는지 알아내는 문제다.

외부 공기와 접촉한 부분이 2부분 이상이면 녹게 되는데, 치즈로 둘러쌓여 있는 부분이면 외부 공기에 해당하지 않는다.

 

문제에서 가장자리들에는 치즈가 놓이지 않는다고 하였기 때문에

초기에 0, 0 에서 탐색을 시작해서 탐색이 가능한 부분이 외부 공기에 해당하는 부분이라고 생각하면 된다.

외부 공기에 해당하는 부분은 3으로 초기화를 해준다음에 치즈의 상하좌우에 3인 부분이 2개 이상이면 제거하는 방식을 사용하였다.

 

치즈 같은 경우는 처음 입력을 받을 때 따로 List를 생성하여 넣어둔다음에 사용하였고,

List에 남아있는 치즈가 없을 때까지 탐색과 치즈 제거를 반복하게 된다.

치즈를 제거 할 때는 제거해야되는 치즈들을 따로 List에 담아 둔 뒤에 전체 탐색을 한 번 끝내고

일괄적으로 제거해주었다.

 

탐색은 dfs, bfs 두 개 모두 코드에 적어 두었다.

설명한 부분에 해당하는 부분은 코드에 주석을 달아두었다.

 

코드

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

public class Main {
	static int[] dx = {0, 0, -1, 1};
	static int[] dy = {-1, 1, 0, 0};
	
	static int N, M;
	static int result;
	static int[][] map;
	static boolean[][] visit;
	static ArrayList<Node> cheese;
	
	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());
		
		map = new int[N][M];
		cheese = new ArrayList<>();
		
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < M; j++) {
				int input = Integer.parseInt(st.nextToken());
				if (input == 1) cheese.add(new Node(i, j));
				map[i][j] = input;
			}
		}
		
		// 치즈 바깥, 즉 외부에 해당하는 부분 탐색
		visit = new boolean[N][M];
		dfs(0, 0);
		//bfs(0, 0);
		
		
		while (!cheese.isEmpty()) { // 남은 치즈가 없을 때까지 탐색
			dayAfter();
			visit = new boolean[N][M];
			dfs(0, 0);
			//bfs(0, 0);
		}
		
		System.out.println(result);
	}
	
	static void dfs(int x, int y) {
		visit[x][y] = true;
		map[x][y] = 3;
		
		for (int i = 0; i < 4; i++) {
			int newX = x + dx[i];
			int newY = y + dy[i];
			
			if (newX < 0 || newX >= N || newY < 0 || newY >= M || visit[newX][newY]) continue;
			if (map[newX][newY] == 0 || map[newX][newY] == 3) {
				dfs(newX, newY);
			}
		}
	}
	
	static void bfs(int x, int y) {
		Queue<Node> q = new LinkedList<>();
		q.offer(new Node(x, y));
		visit[x][y] = true;
		
		while(!q.isEmpty()) {
			Node node = q.poll();
			
			for (int i = 0; i < 4; i++) {
				int newX = node.x + dx[i];
				int newY = node.y + dy[i];
				
				if (newX < 0 || newX >= N || newY < 0 || newY >= M || visit[newX][newY]) continue;
				if (map[newX][newY] == 0 || map[newX][newY] == 3) {
					q.offer(new Node(newX, newY));
					map[newX][newY] = 3;
					visit[newX][newY] = true;
				}
			}
		}
	}
	
	static void dayAfter() {
		ArrayList<Node> next = new ArrayList<>();
		for (int i = 0; i < cheese.size(); i++) {
			Node node = cheese.get(i);
			int cnt = 0;
			
			for (int j = 0; j < 4; j++) {
				int newX = node.x + dx[j];
				int newY = node.y + dy[j];
				
				if (newX < 0 || newX >= N || newY < 0 || newY >= M) continue;
				if (map[newX][newY] == 3) {
					cnt++;
				}
			}
			
			if (cnt >= 2) {
				// 외부와 접촉하는 부분이 2부분 이상일 시
				// 치즈를 리스트에서 제거하고 제거한 만큼 리스트가 줄어들기 떄문에
				// i값도 줄여줌.
				// 추후에 제거된 부분을 추가하기 위해 next 리스트에 추가
				cheese.remove(i);
				i--;
				next.add(node);
			}
		}
		
		for (Node node : next) {
			map[node.x][node.y] = 3;
			// 전체 탐색 완료 후 제거 된 부분을 외부로 변경
		}
		// 하루치 탐색 완료했기 때문에 +1
		result += 1;
	}
}

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