[문제]
철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자모양 상자의 칸에 하나씩 넣은 다음, 상자들을 수직으로 쌓아 올려서 창고에 보관한다.
창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토에 인접한 곳은 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지 그 최소 일수를 알고 싶어 한다.
토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.
[입력]
첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, 1 ≤ H ≤ 100 이다. 둘째 줄부터는 가장 밑의 상자부터 가장 위의 상자까지에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 하나의 상자에 담긴 토마토의 정보가 주어진다. 각 줄에는 상자 가로줄에 들어있는 토마토들의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0 은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다. 이러한 N개의 줄이 H번 반복하여 주어진다.
토마토가 하나 이상 있는 경우만 입력으로 주어진다.
[출력]
여러분은 토마토가 모두 익을 때까지 최소 며칠이 걸리는지를 계산해서 출력해야 한다. 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.
[예제]
>문제 풀이
문제를 잘못 읽어서.. 진짜 한참을 헤맨 문제입니다....ㅎㅏ..
N x M 배열이 H번 반복되어 입력된다는 말을 똑같은 N x M 배열이 H번 쌓여져 있다고 해석해가지고..
(어쩐지..^^ 그렇게 토마토 박스 쌓을거면 2차원 배열 문제랑 뭐가 다른가 한참 생각했네요..쩝..)
문제를 제대로 해석한 후에는, mat[H][N][M] 3차원 배열과 visited[H][N][M] 3차원 배열을 이용해서 기존에 풀었던 토마토 문제(7576번)와 비슷하게 풀었습니다.
**입력
: N x M배열이 H번 반복되어 입력된다.
0: 익지 않은 토마토
1: 익은 토마토
-1: 빈 칸
*익은 토마토를 기준으로 상하좌우의 토마토들이 익어갑니다.
- 0인 경우에 total++ 카운팅을 해줍니다.
후에 cnt(0→1 익어간 토마토들 카운팅)와 비교해서 익지 않은 토마토가 남아있지 않은지 비교해주기 위함입니다. - 1인 경우 큐에 넣어줍니다. 저는 토마토의 위치정보를 Point(int h, int x, int y) 클래스에 담아서 큐에 넣었습니다.
**BFS
증감값은 dx={-1, 1, 0, 0, 0, 0}, dy={0, 0, -1, 1, 0, 0}, dh={0, 0, 0, 0, -1, 1} 배열로 선언해주었습니다.
그리고 큐.isEmpty 일 때 까지
h, x, y= q.poll();
nx=x+dx[i], ny=y+dy[i], nh= h+dh[i];
범위안에 들어오는 0≤nh≤H && 0≤nx≤N && 0≤ny≤M 에 대하여, 방문한적 없고 mat[][][]==0이면
- mat[nh][nx][ny] 방문 처리
- mat[nh][nx][ny]= mat[h][x][y]+1;
- max값 찾기 (날짜 카운팅을 위해서)
- 그리고 큐에 Point(nh, nx, ny)를 넣어주고
- cnt++; (total과 비교해서 0이었던 안익은 토마토들이 다 익었는지 비교하기 위한 변수cnt)
>전체 코드
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
static int N, M, H, total, cnt=0, max=0;
static int mat[][][];
static boolean visited[][][];
static Queue<Point> que;
public static void main(String [] args) {
Scanner scan= new Scanner(System.in);
M= scan.nextInt();
N= scan.nextInt();
H= scan.nextInt();
mat= new int[H][N][M];
visited= new boolean[H][N][M];
que= new LinkedList<Point>();
//입력받기
for(int i=0; i<H; i++) {
for(int j=0; j<N; j++) {
for(int k=0; k<M; k++) {
mat[i][j][k]= scan.nextInt();
if(mat[i][j][k]==1) que.offer(new Point(i,j,k));
if(mat[i][j][k]==0) total++;
}
}
}
if(total==0) System.out.println("0");
else bfs(0,0,0);
}
public static void bfs(int h, int x, int y) {
int nx, ny, nh;
Point p;
int dh[]= {0, 0, 0, 0, -1, 1};
int dx[]= {-1, 1, 0, 0, 0, 0};
int dy[]= {0, 0, -1, 1, 0, 0};
while(!que.isEmpty()) {
p= que.poll();
if(cnt==total) {
System.out.println(max-1);
return;
}
for(int i=0; i<6; i++) {
nh= p.h+dh[i];
nx= p.x+dx[i];
ny= p.y+dy[i];
if(nx<0||nx>=N||ny<0||ny>=M||nh<0||nh>=H) continue;
if(mat[nh][nx][ny]==0&&!visited[nh][nx][ny]) {
visited[nh][nx][ny]=true;
mat[nh][nx][ny]= mat[p.h][p.x][p.y]+1;
max=max>mat[nh][nx][ny]?max:mat[nh][nx][ny];
que.offer(new Point(nh, nx, ny));
cnt++;
}
}
}//while
System.out.println("-1");
}//bfs
static class Point {
int x, y, h;
public Point(int h, int x, int y) {
this.h= h;
this.x= x;
this.y= y;
}
}
}7569번: 토마토
첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100,
www.acmicpc.net
'알고리즘 > 백준 알고리즘' 카테고리의 다른 글
| [백준 알고리즘]1707번 이분 그래프_Java(BFS 풀이) (0) | 2021.05.11 |
|---|---|
| [백준 알고리즘]7562번: 나이트의 이동_Java (0) | 2021.05.08 |
| [백준 알고리즘]2206번: 벽 부수고 이동하기_Java (0) | 2021.05.06 |
| [백준 알고리즘]1697번: 숨바꼭질_Java (0) | 2021.05.04 |
| [백준 알고리즘]7576번: 토마토_Java (0) | 2021.04.30 |
