[백준 / JAVA] 2638. 치즈(G3)

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

 

bfs한번 사방탐색 한번이면 풀 수 있는 데다가 맵 크기도 작아서 골드 3 답지 않은 문제이다.

 

 

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

public class Main {
	static BufferedReader br;
	static BufferedWriter bw;
	static StringTokenizer st;
	static StringBuilder sb;

	public static void main(String[] args) throws Exception {
		br = new BufferedReader(new InputStreamReader(System.in));
		st = new StringTokenizer(br.readLine());
		mapR = Integer.parseInt(st.nextToken());
		mapC = Integer.parseInt(st.nextToken());
		map = new int[mapR][mapC];
		for (int i = 0; i < mapR; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < mapC; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				cheese += map[i][j];
			}
		}
		while (cheese > 0) {
			bfs();
			cheese -= melt();
			time++;
		}
		System.out.println(time);
	}

	static int map[][], mapR, mapC, cheese = 0, time = 0, dr[] = { -1, 1, 0, 0 }, dc[] = { 0, 0, -1, 1 };

	static int melt() {
		Deque<Point> dq = new ArrayDeque<>();
		int cnt;
		for (int r = 0; r < mapR; r++)
			for (int c = 0; c < mapC; c++) {
				cnt = 0;
				if (map[r][c] == 1) {
					for (int d = 0; d < 4; d++) {
						int nr = r + dr[d];
						int nc = c + dc[d];
						if (nr < 0 || nr >= mapR || nc < 0 || nc >= mapC || map[nr][nc] < 2)
							continue;
						cnt++;
					}
				}
				if (cnt > 1)
					dq.add(new Point(r, c));
			}
		int size = dq.size();
		while (!dq.isEmpty()) {
			Point cur = dq.poll();
			map[cur.row][cur.col] = 2;
		}
		return size;
	}

	static void bfs() { // 외부 칠하기
		Deque<Point> dq = new ArrayDeque<>();
		boolean visited[][] = new boolean[mapR][mapC];
		dq.add(new Point(0, 0));
		visited[0][0] = true;
		map[0][0] = 2;
		while (!dq.isEmpty()) {
			Point cur = dq.poll();
			for (int d = 0; d < 4; d++) {
				int nr = cur.row + dr[d];
				int nc = cur.col + dc[d];
				if (nr < 0 || nr >= mapR || nc < 0 || nc >= mapC || visited[nr][nc] || map[nr][nc] == 1)
					continue;
				dq.add(new Point(nr, nc));
				visited[nr][nc] = true;
				map[nr][nc] = 2;
			}
		}
	}

	static class Point {
		int row, col;

		public Point(int row, int col) {
			this.row = row;
			this.col = col;
		}
	}
}