TIL(Today I Learned)
[TIL] 99클럽 코테 스터디 12일차 TIL + 백준 7569 토마토
zincah
2024. 11. 9. 00:10
반응형

문제 풀이

문제 탐색하기
너비우선탐색 알고리즘을 활용하여 문제 풀면 토마토가 모두 익을때까지 며칠이 걸리는 지 구할 수 있습니다.
익은 토마토가 있는 위치를 모두 큐에 넣어서 x축 y축 z축 모든 곳의 토마토를 탐색하여 익지 않은 토마토의 위치값을 증가시키며 다시 큐에 담습니다. (토마토는 3단 배열에 담아지게 되는데 익지 않은 토마토를 만났을 때 기존 탐색 노드 위치값 + 1로 위치값을 세팅해주면 됩니다.)
이렇게 탐색을 반복하다가 탐색이 모두 끝났을 때 익지 않은 토마토가 하나라도 있으면 -1을 출력하고 모든 토마토가 익었을 때 증가시켰던 토마토의 위치값에서 -1을 한 값을 출력해주면 토마토가 모두 익는 최소 일자를 구할 수 있습니다.
문제 풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
class PointXYZ{
int z;
int y;
int x;
public PointXYZ(int z, int y, int x){
this.z = z;
this.y = y;
this.x = x;
}
}
public class Main {
static int[] xArr = {-1, 0, 1, 0, 0, 0};
static int[] yArr = {0, 1, 0, -1, 0, 0};
static int[] hArr = {0, 0, 0, 0, 1, -1};
static int M, N, H;
static int[][][] arr;
static Queue<PointXYZ> queue;
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());
arr = new int[H+1][N+1][M+1];
queue = new LinkedList<>();
for(int i=1; i<=H; i++){
for(int j=1; j<=N; j++){
st = new StringTokenizer(br.readLine());
for(int k=1; k<=M; k++){
arr[i][j][k] = Integer.parseInt(st.nextToken());
if(arr[i][j][k] == 1){
queue.add(new PointXYZ(i, j, k));
}
}
}
}
System.out.println(bfs());
}
private static int bfs(){
while(!queue.isEmpty()){
PointXYZ point = queue.poll();
int z = point.z;
int y = point.y;
int x = point.x;
for(int i=0; i<6; i++){
int newZ = z + hArr[i];
int newY = y + yArr[i];
int newX = x + xArr[i];
if(checkPoint(newX, newY, newZ)){
queue.add(new PointXYZ(newZ, newY, newX));
arr[newZ][newY][newX] = arr[z][y][x] + 1;
}
}
}
int result = Integer.MIN_VALUE;
for(int i=1; i<=H; i++){
for(int j=1; j<=N; j++){
for(int k=1; k<=M; k++){
if(arr[i][j][k] == 0) return -1;
result = Math.max(result, arr[i][j][k]);
}
}
}
return result-1;
}
private static boolean checkPoint(int x, int y, int z){
if(x < 1 || x > M || y < 1 || y > N || z < 1 || z > H){
return false;
}
if(arr[z][y][x] == 0){
return true;
}else{
return false;
}
}
}
오늘의 회고
알고리즘을 파악해도 해당 알고리즘을 어떻게 활용해서 문제를 풀것인지도 중요한 것 같습니다. 오늘 문제는 아이디어를 떠오르지 않아 결국 도움을 받아 문제를 풀었는데 비슷한 문제를 여러번 풀면서 이런 패턴에도 익숙해져야할 것 같습니다ㅜㅜ..
반응형