7569 토마토
문제 이해
3차원 배열이 존재한다.
1은 익은 토마토, 0은 익지 않은 토마토, -1은 토마토가 들어 있지 않은 칸이다.
이 때, 익은 토마토는 하루에 한 번씩 익지 않은 토마토를 익게 한다.
익게 되는 토마토는 위쪽, 아래쪽, 그리고 같은 층의 상하좌우에 존재하는 익지 않은 토마토이다.
토마토가 들어있지 않은 칸은 토마토가 없으므로 토마토가 익을 수도, 익힐 수도 없다.
이 때 모든 토마토가 익을 때까지 걸리는 최소 시간을 출력하는 문제이다.
문제 풀이
처음에 익지 않은 토마토 개수를 A라고 가정하자.
이 때 토마토가 한 개 익을 때마다 A를 1씩 감소시키면, A = 0이 되는 순간이 모든 토마토가 익은 순간이 될 것이다.
재귀함수를 사용하면 A = 0이 되는 순간을 처리하기 어려울 것이라는 생각을 하여 BFS를 통해 문제를 해결하기로 하였다.
먼저 익은 토마토의 위치를 저장해 놓을 것이다.
이후, 일자에 따라 토마토의 상하좌우, 위 아래에 존재하는 익지 않은 토마토를 익힐 것이다. 마지막으로, 익은 토마토가 인접한 모든 토마토를 익혔으면 다음부터는 이 토마토는 더 이상 익힐 토마토가 없으므로 더 이상 Search 하지 않아도 된다.
따라서, visit을 true로 만들어준다.
마지막으로 A = 0이 되기 직전에 내가 Search 했던 좌표의 토마토가 익을 때 까지 걸린 시간이 정답이 될 것이다.
코드
import java.io.*;
import java.util.*;
class Tomato{
int x;
int y;
int z;
int day;
public Tomato(int x,int y,int z,int day) {
this.x = x;
this.y = y;
this.z = z;
this.day = day;
}
}
public class Main {
static StringBuilder sb = new StringBuilder();
static int N, M, H;
static int[][][] arr;
static int need_fill = 0;
static Queue<Tomato> sub = new LinkedList<>();
static Integer bfs() {
int day = -1;
need_fill+=sub.size();
while(!sub.isEmpty()) {
if(need_fill==0) return day;
// 익힐 토마토가 없으므로 모든 토마토가 익었다.
// 따라서 직전에 검사한 토마토가 익을 때까지의 시간이 저장된
// day를 반환시킨다.
Tomato tmp = sub.poll();
if(tmp.x<0 || tmp.y<0 || tmp.z<0 || tmp.x>=N || tmp.y>=M
|| tmp.z>=H) continue;
if(arr[tmp.x][tmp.y][tmp.z]!=0) continue;
// 해당 위치는 이미 익은 토마토이거나, 토마토가 없는 곳이다.
// 따라서 생략한다.
arr[tmp.x][tmp.y][tmp.z] = 1;
need_fill--;
// 처음으로 익지 않은 토마토가 익었다.
// 따라서, 익지 않은 토마토 개수를 1개 빼준다.
day = tmp.day;
// 우리는 need_fill = 0이 되기 "직전"에 검사하는 위치의
// 토마토가 익을 때까지 걸린 시간이 필요하다
// 따라서, day 공간에 계속해서 현재 검사하고 있는 익지 않은
// 토마토가 익을 때까지 걸린 시간을 저장할 필요가 있다.
sub.add(new Tomato(tmp.x+1,tmp.y,tmp.z,tmp.day+1));
sub.add(new Tomato(tmp.x-1,tmp.y,tmp.z,tmp.day+1));
sub.add(new Tomato(tmp.x,tmp.y+1,tmp.z,tmp.day+1));
sub.add(new Tomato(tmp.x,tmp.y-1,tmp.z,tmp.day+1));
sub.add(new Tomato(tmp.x,tmp.y,tmp.z+1,tmp.day+1));
sub.add(new Tomato(tmp.x,tmp.y,tmp.z-1,tmp.day+1));
}
return -1;
// 이곳에 도착했다는 것은 need_fill = 0인 Case가 없었다는 의미이다.
// 즉, 모든 토마토가 익지 않았으므로 -1을 반환한다.
}
public static void main(String[] args) {
FastReader sc = new FastReader();
M = sc.nextInt();
N = sc.nextInt();
H = sc.nextInt();
arr = new int[N][M][H];
for(int k =0;k<H;k++) {
for(int i = 0;i<N;i++) {
for(int j =0;j<M;j++) {
int tmp = sc.nextInt();
switch(tmp) {
case 0:
need_fill++;
break;
case 1:
sub.add(new Tomato(i,j,k,0));
tmp = 0;
break;
}
arr[i][j][k] = tmp;
}
}
}
System.out.println(bfs());
}
static class FastReader // 빠른 입력을 위한 클래스
}
결과
import java.io.*;
import java.util.*;
class Tomato{
int x;
int y;
int z;
int day;
public Tomato(int x,int y,int z,int day) {
this.x = x;
this.y = y;
this.z = z;
this.day = day;
}
}
public class Main {
static StringBuilder sb = new StringBuilder();
static int N, M, H;
static int[][][] arr;
static int need_fill = 0;
static Queue<Tomato> sub = new LinkedList<>();
static Integer bfs() {
int day = -1;
need_fill+=sub.size();
while(!sub.isEmpty()) {
if(need_fill==0) return day;
// 익힐 토마토가 없으므로 모든 토마토가 익었다.
// 따라서 직전에 검사한 토마토가 익을 때까지의 시간이 저장된
// day를 반환시킨다.
Tomato tmp = sub.poll();
if(tmp.x<0 || tmp.y<0 || tmp.z<0 || tmp.x>=N || tmp.y>=M
|| tmp.z>=H) continue;
if(arr[tmp.x][tmp.y][tmp.z]!=0) continue;
// 해당 위치는 이미 익은 토마토이거나, 토마토가 없는 곳이다.
// 따라서 생략한다.
arr[tmp.x][tmp.y][tmp.z] = 1;
need_fill--;
// 처음으로 익지 않은 토마토가 익었다.
// 따라서, 익지 않은 토마토 개수를 1개 빼준다.
day = tmp.day;
// 우리는 need_fill = 0이 되기 "직전"에 검사하는 위치의
// 토마토가 익을 때까지 걸린 시간이 필요하다
// 따라서, day 공간에 계속해서 현재 검사하고 있는 익지 않은
// 토마토가 익을 때까지 걸린 시간을 저장할 필요가 있다.
sub.add(new Tomato(tmp.x+1,tmp.y,tmp.z,tmp.day+1));
sub.add(new Tomato(tmp.x-1,tmp.y,tmp.z,tmp.day+1));
sub.add(new Tomato(tmp.x,tmp.y+1,tmp.z,tmp.day+1));
sub.add(new Tomato(tmp.x,tmp.y-1,tmp.z,tmp.day+1));
sub.add(new Tomato(tmp.x,tmp.y,tmp.z+1,tmp.day+1));
sub.add(new Tomato(tmp.x,tmp.y,tmp.z-1,tmp.day+1));
}
return -1;
// 이곳에 도착했다는 것은 need_fill = 0인 Case가 없었다는 의미이다.
// 즉, 모든 토마토가 익지 않았으므로 -1을 반환한다.
}
public static void main(String[] args) {
FastReader sc = new FastReader();
M = sc.nextInt();
N = sc.nextInt();
H = sc.nextInt();
arr = new int[N][M][H];
for(int k =0;k<H;k++) {
for(int i = 0;i<N;i++) {
for(int j =0;j<M;j++) {
int tmp = sc.nextInt();
switch(tmp) {
case 0:
need_fill++;
break;
case 1:
sub.add(new Tomato(i,j,k,0));
tmp = 0;
break;
}
arr[i][j][k] = tmp;
}
}
}
System.out.println(bfs());
}
static class FastReader // 빠른 입력을 위한 클래스
}
Author And Source
이 문제에 관하여(7569 토마토), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@idj7183/7569-토마토저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)