[백준] Q7569_토마토
✨Link Q7569_토마토
🤔 문제
창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토에 인접한 곳은 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지 그 최소 일수를 알고 싶어 한다.
토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.
입력
첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, 1 ≤ H ≤ 100 이다. 둘째 줄부터는 가장 밑의 상자부터 가장 위의 상자까지에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 하나의 상자에 담긴 토마토의 정보가 주어진다. 각 줄에는 상자 가로줄에 들어있는 토마토들의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0 은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다. 이러한 N개의 줄이 H번 반복하여 주어진다.
토마토가 하나 이상 있는 경우만 입력으로 주어진다.
예제입력--->
5 3 1
0 -1 0 0 0
-1 -1 0 1 1
0 0 0 1 1
출력
여러분은 토마토가 모두 익을 때까지 최소 며칠이 걸리는지를 계산해서 출력해야 한다. 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.
예제출력 --->
-1
💡 접근
Q5676_토마토 문제와 풀이가 비슷했다. 높이만 추가 되니까 2차원 배열에서 3차원 배열로 만들어 준다. 그 외에는 동일하다.
💻 코드(1)_나의 풀이
import org.w3c.dom.Node;
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 Q7569 {
static int[][][] map;//3차 배열 사용
static int h,n,m;
static int day = 0;
static Queue<Node> queue;
static int[] dh={0,0,0,0,-1,1};
static int[] dx={-1,0,1,0,0,0};
static int[] dy={0,1,0,-1,0,0};
static class Node{
int z,x,y;
int day;
public Node(int z, int x, int y, int day){
this.z=z;
this.x=x;
this.y=y;
this.day=day;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st=new StringTokenizer(br.readLine());
m = Integer.parseInt(st.nextToken());
n = Integer.parseInt(st.nextToken());
h = Integer.parseInt(st.nextToken());
map = new int[h][n][m];
queue = new LinkedList();
for(int i=0;i<h;i++){//높이가 추가되면서 3중 for문 사용
for(int j=0;j<n;j++){
st=new StringTokenizer(br.readLine());
for(int k=0;k<m;k++){
map[i][j][k] = Integer.parseInt(st.nextToken());
if(map[i][j][k]==1){
queue.offer(new Node(i,j,k,0));//0일째 익은 토마토들을 큐에 담기(초기화)
}
}
}
}
bfs();
for(int i=0;i<h;i++){
for(int j=0;j<n;j++){
for(int k=0;k<m;k++){
if(map[i][j][k]==0){//익지 않은 토마토가 있다면
System.out.println(-1);
System.exit(0);
}
}
}
}
System.out.println(day);//마지막으로 익은 토마토 day(제일 큰)값
}
public static void bfs(){
while(!queue.isEmpty()){
Node node = queue.poll();
for(int i=0;i<6;i++){
int z = node.z+dh[i];
int x = node.x+dx[i];
int y = node.y+dy[i];
if(z>=0&&z<h && x>=0&&x<n && y>=0&&y<m){
if(map[z][x][y]==0){//인접 토마토가 익지 않은 토마토일때
queue.add(new Node(z,x,y,node.day+1));//다음날
map[z][x][y]=1;
day = Math.max(day,node.day+1);
}
}
}
}
}
}
- 높이가 추가되면서 3차배열, 3중포문을 사용했다. 풀이방법은 Q5676_토마토와 동일하다!
Author And Source
이 문제에 관하여([백준] Q7569_토마토), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@ehddek/백준-Q7569토마토저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)