2636번 : 치즈 [Java]

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

2636번: 치즈

해결 방법

가장자리부터 탐색을 해야 하기 때문에 (0,0)부터 BFS를 진행한다. 만약 (i, j)가 1로 치즈인 경우엔 방문 체크를 하고 치즈 수를 줄인 뒤 다음 턴엔 공기가 되도록 0으로 바꾸어준다. (i, j)가 0으로 공기인 경우 방문 체크를 해주고 사방 탐색을 진행을 위해 큐에 넣어준다.

 

전체 코드

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 {
	static class Point {
		int x, y;

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

	static int N, M;
	static int[][] map;
	static int cheese, temp;
	static int time;
	static boolean[][] visited;
	static int[] dr = { -1, 0, 1, 0 };
	static int[] dc = { 0, 1, 0, -1 };

	public static void main(String[] args) throws IOException {
		BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(input.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(input.readLine(), " ");
			for (int j = 0; j < M; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				if (map[i][j] == 1) 
					cheese++;
			}
		}

		while (true) {
			if (cheese == 0)
				break;

			time++;
			temp = cheese; 
			bfs();
		}
		
		System.out.println(time);
		System.out.println(temp);
	}

	private static void bfs() {
		Queue<Point> queue = new LinkedList<Point>();
		visited = new boolean[N][M];

		queue.add(new Point(0, 0));
		visited[0][0] = true;

		while (!queue.isEmpty()) {
			Point p = queue.poll();
			for (int d = 0; d < 4; d++) {
				int nr = p.x + dr[d];
				int nc = p.y + dc[d];

				if (nr < 0 || nc < 0 || nr >= N || nc >= M)
					continue;

				if (visited[nr][nc])
					continue;

				if (map[nr][nc] == 1) {
					visited[nr][nc] = true;
					map[nr][nc] = 0;
					cheese--;
					continue;
				}
                
				queue.add(new Point(nr, nc));
				visited[nr][nc] = true;
			}
		}

	}
}