백준 2638번 : 치즈 [Java]

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

 

문제 탐색하기

접근법이 어렵지 않은 구현 문제이다. N * M 모눈종이 위의 치즈가 특정 조건에 따라서 시간마다 사라지는데, 이를 구현하면 된다. 치즈가 사라지는 조건은 아래와 같다.

• 4면 중 2면 이상이 공기 (0)와 맞닿아 있을 때 1시간 후 치즈는 사라진다.

위 조건대로 구현하면 되는데 한 가지 생각해봐야 할 것은 치즈 내부에 갇혀 있는 공간은 그저 빈 공간일 뿐 외부 공기로 취급하지 않는 다는 점이다. 매 입력마다 제일 가장자리에 해당하는 부분은 외부 공기로 취급되기 때문에 이를 이용하면 어떤 부분까지가 외부 공기인지 판별할 수 있다.

 

위의 외부 공기 판별을 bfs를 통해서 매번 찾고 실제로 없어지는 치즈를 찾으면 정답을 받을 수 있을 것이다.

 

코드 구현하기

1. 입력을 처리한다. 2개의 2차원 배열을 통해서 외부 공기와 실제 치즈의 상태를 확인한다.
2. 반복문을 통해서 치즈가 전부 사라질 때까지 아래를 반복한다.
   1. 임시 리스트를 만들고 bfs를 통해 외부 공기를 판별한다.
   2. 모든 치즈에 대해서 치즈와 인접한 4면을 검사한다. 이 때 외부 공기인지 판별된 배열을 통해서 실제 외부 공기와 접촉했는지 알 수 있다.
   3. 기존 리스트를 임시 리스트로 치환한다.
   4. 시간에 1을 더한다.
3. 걸린 시간을 출력한다.

풀이

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

public class Main {
	public static class FastReader {
	    BufferedReader br;
	    StringTokenizer st;

	    public FastReader() {
	        br = new BufferedReader(new InputStreamReader(System.in));
	    }

	    String next() {
	        while (st == null || !st.hasMoreElements()) {
	            try {
	                st = new StringTokenizer(br.readLine());
	            } catch (IOException e) {
	                e.printStackTrace();
	            }
	        }

	        return st.nextToken();
	    }

	    int nextInt() {
	        return Integer.parseInt(next());
	    }
	}

	static int N, M, answer = 0;
	static int[][] map;
	static boolean[][] visited;
	static int[] dx = {-1, 0, 1, 0};
	static int[] dy = {0, -1, 0, 1};
	static ArrayList<Cheese> cheeseBox = new ArrayList<>();

	static class Cheese {
		int x, y;

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

	static void bfs() {
		visited = new boolean[N][M];
		LinkedList<Cheese> q = new LinkedList<>();
		visited[0][0] = true;
		q.add(new Cheese(0, 0));
		while (!q.isEmpty()) {
			Cheese now = q.poll();
			for (int i = 0; i < 4; i++) {
				int nx = now.x + dx[i];
				int ny = now.y + dy[i];

				if (nx < 0 || ny < 0 || nx >= N || ny >= M || visited[nx][ny]) {
					continue;
				}

				if (map[nx][ny] == 0) {
					visited[nx][ny] = true;
					q.add(new Cheese(nx, ny));
				}
			}
		}
	}

	static void print() {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				System.out.print(visited[i][j] + " ");
			}
			System.out.println();
		}
		System.out.println("__________________________");
	}

	public static void main(String[] args) {
		FastReader fr = new FastReader();
		N = fr.nextInt();
		M = fr.nextInt();
		map = new int[N][M];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				int now = fr.nextInt();
				map[i][j] = now;
				if (now == 1) {
					cheeseBox.add(new Cheese(i, j));
				}
			}
		}

		while (!cheeseBox.isEmpty()) {
			ArrayList<Cheese> temp = new ArrayList<>();
			bfs();
			for (Cheese cheese : cheeseBox) {
				int count = 0;
				for (int i = 0; i < 4; i++) {
					int nx = cheese.x + dx[i];
					int ny = cheese.y + dy[i];
					if (nx < 0 || ny < 0 || nx >= N || ny >= M) {
						continue;
					}
					if (map[nx][ny] == 0 && visited[nx][ny]) {
						count++;
					}
				}

				if (count >= 2) {
					map[cheese.x][cheese.y] = 0;
				} else {
					temp.add(cheese);
				}
			}
			answer++;
			cheeseBox = temp;
		}

		System.out.println(answer);
	}
}