백준 문제 10699번 토마토

문제 풀러 Go

7569번: 토마토

 

백준 문제 10699번 토마토

---

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class Pos{
	public Pos() {}
	public Pos(int width, int length, int height, int day) {
		this.width = width;
		this.length = length;
		this.height = height;
		this.day = day;
	}
	public void setPos(int width, int length, int height, int day) {
		this.width = width;
		this.length = length;
		this.height = height;
		this.day = day;
	}
	int width; //가로
	int length; //세로
	int height; //높이
	int day = -1;//지난날짜
}

public class Main {

	static int[][][] array = new int[100][100][100];
	
	public static void main(String[] args) {
		
		int N,M; //상자의 크기
		int H; //상자의 수
		Pos ripeTomato = new Pos();
		
		Scanner scan = new Scanner(System.in);
		
		Queue<Pos> q = new LinkedList<>();
		
		M = scan.nextInt(); //열
		N = scan.nextInt(); //행
		H = scan.nextInt(); //높이
		
		boolean found[][][] = new boolean[H][N][M]; //익은 토마토는 있었지만 익지 않았다면 -1
		int tempArray[][][] = new int[H][N][M];
		for (int boxCnt = 0; boxCnt < H; boxCnt++) {
			for(int x = 0; x < N; x++) {
				for(int y = 0; y < M; y++) {
					array[boxCnt][x][y] = scan.nextInt();
					tempArray[boxCnt][x][y] = array[boxCnt][x][y];
					if(array[boxCnt][x][y] ==1) {
						q.add(new Pos(y, x, boxCnt, 0)); //start
						found[boxCnt][x][y] = true;
					}
				}
			}
		}
		
		int res = -1;
		if(!q.isEmpty()) {
			//BFS

			Pos now = new Pos(), next= new Pos();
		
			int deltaH[] = {0, 0, 0, 0, -1, 1};
			int deltaL[] = {-1, 1, 0, 0, 0, 0};
			int deltaW[] = {0, 0, -1, 1, 0, 0};
			
			while(!q.isEmpty()) {
				now = q.poll();
				
				//마지막 now의 day가 일수일 것이다.
				for (int i = 0; i < deltaW.length; i++) {
					next = new Pos(now.width+ deltaW[i], now.length+ deltaL[i], now.height+ deltaH[i], now.day+1);
					if(next.height >= H || next.length >= N || next.width >= M||
							next.height < 0 || next.length < 0 || next.width < 0) {continue;}
					if(found[next.height][next.length][next.width]) {continue;}
					if(array[next.height][next.length][next.width]!= 0) {continue;}
					found[next.height][next.length][next.width] = true;
					tempArray[next.height][next.length][next.width] = 1;
					q.add(next);
				}
			}
			res = now.day;
			for (int boxCnt = 0; boxCnt < H; boxCnt++) {
				for(int x = 0; x < N; x++) {
					for(int y = 0; y < M; y++) {
						if(tempArray[boxCnt][x][y] == 0){
							res = -1;
							break;
						}
					}
				}
			}
		}
		System.out.println(res);
		
	}
}

코드 정말 길다,, 그리고 이건 정말 어렵게 풀었다.. 이것도 BFS로 풀었다.

내가 생각하지 못했던 부분은 익은 토마토가 여러개일 수도 있다는 것이다.

처음에는 익은 토마토가 한개라는 가정을 하고 풀었다. 그런데 그게 아니었다.

그렇게 때문에 처음에 queue 공간에 익은 토마토들을 넣어놓고, 0일이 지난 것으로 하고, queue구조이니 앞에서부터 빼오면서 위, 아래, 좌, 우, 상, 하를 조사하고 날짜를 1씩 더해야하는 것이었다.

 

자세한 코드의 설명은 시간이 나면 하도록 해야겠다.

 

아무튼 어제 풀었는데, 문제 파악을 제대로 할 수 있도록 해야겠다.

실수와 실수를 해결한 방법을 기록해두어서 더욱 발전하는 내가 되고 싶다.