치즈
백준 2636: 치즈
풀이
BFS를 이용
녹을 치즈를 저장해 놓았다가 탐색이 끝난 후 한꺼번에 치즈를 녹이는 것이 중요
처음 1시간 안에 치즈가 다 녹을 수 있음을 주의
->그래서 처음 입력 받을 때부터 치즈조각 개수를 세어줌
소스코드
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
static class Node {
int r, c;
Node(int r, int c) {
this.r = r;
this.c = c;
}
}
static int[] dr = { -1, 1, 0, 0 };
static int[] dc = { 0, 0, -1, 1 };
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int h = sc.nextInt(); // 판의 세로의 길이(행)
int w = sc.nextInt(); // 판의 가로의 길이(열)
int[][] map = new int[h][w];
int cheese = 0; //치즈조각의 개수
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
map[i][j] = sc.nextInt();
if(map[i][j]==1)
cheese++;
}
}
int time = 0;
Queue<Node> queue = new LinkedList<>();
boolean flag = true;
while (flag) {
time++;
boolean visited[][] = new boolean[h][w];
queue.add(new Node(0, 0));
visited[0][0] = true;
while (!queue.isEmpty()) {
Node node = queue.poll();
for (int d = 0; d < 4; d++) {
int nr = node.r + dr[d];
int nc = node.c + dc[d];
if (nr >= 0 && nc >= 0 && nr < h && nc < w && !visited[nr][nc]) {
if (map[nr][nc] == 0) {
queue.add(new Node(nr, nc));
visited[nr][nc] = true;
} else if (map[nr][nc] == 1) {
map[nr][nc] = 2; // 녹을 자리이면 그 곳을 2로 바꿔준다
}
}
}
}
// 치즈 녹이기
int cnt = 0; // 현재 치즈조각 개수
boolean check = false; //다음에 녹을 치즈가 남아있는지 확인하기 위해
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
if (map[i][j] == 2) {
map[i][j] = 0;
} else if (map[i][j] == 1) {
cnt++;
check = true;
}
}
}
if(check) //녹을 치즈가 있으면 현재까지의 치즈조각 개수 저장
cheese = cnt;
if(!check) //더이상 녹을 치즈가 없으면 끝내기
flag = false;
}
System.out.println(time);
System.out.println(cheese);
}
}