문제
https://www.acmicpc.net/problem/7569
난이도 : 골드5
풀이
- 3차원 배열에서 1(익은 토마토)에 인접한 값이 0(안 익은 토마토)인 위치를 탐색해서 1로 변경해나가야 한다.
- 탐색이 끝나는 최소 일수를 구해야 하므로 BFS를 사용하였다.
- 시간 복잡도 : O(M * N * H)
- 2 ≤ M, N ≤ 100, 1 ≤ H ≤ 100 이므로 최대 1,000,000으로 시간제한을 통과한다.
- 3차원 배열이므로 x,y,z 6가지 방향으로 탐색한다.
- 요구사항에 따라 탐색 종료 후 배열에 0(안 익은 토마토) 존재할 경우, -1을 출력하고 존재하지 않을 경우 BFS의 최대 깊이를 출력한다.
코드
import java.io.*;
import java.util.*;
public class Main{
static int max = 0;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int m = Integer.parseInt(st.nextToken());
int n = Integer.parseInt(st.nextToken());
int h = Integer.parseInt(st.nextToken());
int[][][] tomatoes = new int[m][n][h];
for(int i=0;i<h;i++){
for(int j=0;j<n;j++){
st = new StringTokenizer(br.readLine());
for(int k=0;k<m;k++){
tomatoes[k][j][i] = Integer.parseInt(st.nextToken());
}
}
}
bfs(tomatoes);
for(int i=0;i<h;i++){
for(int j=0;j<n;j++){
for(int k=0;k<m;k++){
if(tomatoes[k][j][i] == 0) {
System.out.print(-1);
return;
}
}
}
}
System.out.print(max);
}
static void bfs(int[][][] tomatoes){
Queue<Tomato> q = new LinkedList<>();
for(int i=0;i<tomatoes.length;i++){
for(int j=0;j<tomatoes[0].length;j++){
for(int k=0;k<tomatoes[0][0].length;k++){
if(tomatoes[i][j][k] == 1) q.add(new Tomato(i, j, k, 0));
}
}
}
while(!q.isEmpty()){
Tomato now = q.poll();
max = Math.max(max, now.depth);
int[] dx = {1, -1, 0, 0, 0, 0};
int[] dy = {0, 0, 1, -1, 0, 0};
int[] dz = {0, 0, 0, 0, 1, -1};
for(int i=0;i<dx.length;i++){
int newX = now.x + dx[i];
int newY = now.y + dy[i];
int newZ = now.z + dz[i];
if(newX < 0 || newX >= tomatoes.length) continue;
if(newY < 0 || newY >= tomatoes[0].length) continue;
if(newZ < 0 || newZ >= tomatoes[0][0].length) continue;
if(tomatoes[newX][newY][newZ] != 0) continue;
q.add(new Tomato(newX, newY, newZ, now.depth+1));
tomatoes[newX][newY][newZ] = 1;
}
}
}
static class Tomato{
int x;
int y;
int z;
int depth;
Tomato(int x, int y, int z, int depth){
this.x = x;
this.y = y;
this.z = z;
this.depth = depth;
}
}
}
'Problem Solving' 카테고리의 다른 글
[백준] 10026번: 적록색약 (Java) (0) | 2024.08.29 |
---|---|
[백준] 2206번: 벽 부수고 이동하기 (Java) (0) | 2024.08.29 |
[백준] 2470번: 두 용액 (Java) (5) | 2024.08.28 |
[프로그래머스] 부대복귀 (Java) (2) | 2024.08.27 |
[백준] 16928번: 뱀과 사다리 게임 (Java) (0) | 2024.08.27 |