[Algorithm/Java] 백준 7569번 - 토마토
https://www.acmicpc.net/problem/7569
📌 문제
문제 유형
- 그래프
문제 설명
철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자모양 상자의 칸에 하나씩 넣은 다음, 상자들을 수직으로 쌓아 올려서 창고에 보관한다.
창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다.
하나의 토마토에 인접한 곳은 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다.
철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지 그 최소 일수를 알고 싶어 한다.
토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라.
단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.
입출력 예시
입력
첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, 1 ≤ H ≤ 100 이다.
둘째 줄부터는 가장 밑의 상자부터 가장 위의 상자까지에 저장된 토마토들의 정보가 주어진다.
즉, 둘째 줄부터 N개의 줄에는 하나의 상자에 담긴 토마토의 정보가 주어진다. 각 줄에는 상자 가로줄에 들어있는 토마토들의 상태가 M개의 정수로 주어진다.
정수 1은 익은 토마토, 정수 0 은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다. 이러한 N개의 줄이 H번 반복하여 주어진다.
토마토가 하나 이상 있는 경우만 입력으로 주어진다.
5 3 2
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 1 0 0
0 0 0 0 0
출력
여러분은 토마토가 모두 익을 때까지 최소 며칠이 걸리는지를 계산해서 출력해야 한다.
만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.
4
🔍 문제 풀이
① 먼저 배열을 순회하며 1(모든 익은 토마토)를 큐에 넣는다.
여러 위치에서 동시에 익기 시작하므로, BFS의 시작점이 여러 개다.
② BFS로 상하좌우위아래 총 6방향을 탐색한다.
3차원 배열이므로 dx, dy, dz 방향 배열을 사용하여 인접 칸을 순회한다.
③ graph[nz][nx][ny] = graph[cz][cx][cy] + 1로 날짜를 누적한다
처음 익은 토마토가 1이므로, 나중에 최대값에서 -1을 해주면 실제 걸린 날짜가 된다.
④ 탐색이 끝난 후, 모든 0이 1 이상으로 바뀌었는지 확인한다.
→ 만약 익지 못한 토마토(0)가 남아 있다면 -1 출력
→ 그렇지 않다면 max - 1 출력
💻 전체 코드
import java.io.*;
import java.util.*;
public class Main {
static int m, n, h;
static int[][][] graph;
static int[] dz = {-1, 1, 0, 0, 0, 0};
static int[] dx = {0, 0, -1, 1, 0, 0};
static int[] dy = {0, 0, 0, 0, -1, 1};
static void bfs(Deque<int[]> dq){
while(!dq.isEmpty()){
int[] current = dq.poll();
int cz = current[0];
int cx = current[1];
int cy = current[2];
for(int i=0; i<6; i++){
int nz = cz + dz[i];
int nx = cx + dx[i];
int ny = cy + dy[i];
if(nz < 0 || nz >= h || nx < 0 || nx >= n || ny < 0 || ny >=m) continue;
if(graph[nz][nx][ny] == 0){
graph[nz][nx][ny] = graph[cz][cx][cy] + 1;
dq.offer(new int[]{nz, nx, ny});
}
}
}
}
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()); // 높이
graph = new int[h][n][m];
Deque<int[]> dq = new ArrayDeque<>();
// 입력 받기 및 deque에 넣기
for(int z=0; z<h; z++){
for(int i=0; i<n; i++){
st = new StringTokenizer(br.readLine());
for(int j=0; j<m; j++){
graph[z][i][j] = Integer.parseInt(st.nextToken());
if(graph[z][i][j] == 1){
dq.offer(new int[]{z, i, j});
}
}
}
}
// bfs 호출
bfs(dq);
// 출력
int max = Integer.MIN_VALUE;
for(int z=0; z<h; z++){
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
if(graph[z][i][j] == 0){
System.out.println(-1);
return;
}
max = Math.max(max, graph[z][i][j]);
}
}
}
System.out.println(max - 1);
}
}
💭 배운 점
처음에는 그냥 BFS만 잘 돌리면 된다고 생각했는데, 시작 지점을 큐에 먼저 다 넣어야 한다는 개념을 놓쳤다.
익은 토마토가 여러 개일 수 있다는 걸 고려하지 못해, 하나씩만 처리하려다 전파가 제대로 되지 않았고 결국 문제를 풀 수 없었다.
다음 문제를 풀 때는 BFS 시작 지점을 어떻게 설정할지 먼저 생각해보자.
댓글남기기