[백준] 7569. 토마토 - 실버1

https://www.acmicpc.net/problem/7569

7569번: 토마토

 

문제 요약

https://sigidev.tistory.com/21 이 문제의 3차원 버전이다.

토마토 상자가 한 박스가 아니라 여러 박스일 때 최소 일수를 구한다.

 

문제 해결 아이디어

3차원 배열과 친하지 않아서 그냥 2차원 배열로 입력을 받고 인덱스를 조절해 줬다. 행은 N*H만큼 들어오니 그 부분만 바뀌었다.

또 하나 추가된 점은 전 문제에서는 무조건 익은 토마토가 1개 이상이었는데 여기서는 0일 때도 생각해 줘야 돼서 queue.size == 0이면 강제종료 시키는 코드를 집어넣었다. 저번에 한번 써먹은 이후로 계속 System.exit(0); 쓰고 있는데 사실 이걸 계속 쓰는건 좋지 않을 것 같다는 생각이 든다...

방향을 관리하는 배열에 위 아래, 즉 이전 혹은 다음 상자로 넘어가는 방향을 추가했다. 

order 변수를 넣어 현재 확인하고 있는 토마토가 몇 번째 상자에 있는지를 저장해 주었다. x좌표를 / N으로 나누면 값이 나온다.

전 문제와 같은 앞 뒤 양옆, 즉 2차원 공간에 대한 부분은 행은 현재 상자의 위치에 있어야 하고, 즉 order보다 크거나 같고 (order + 1) * N을 넘지 않아야 한다. 열은 동일하다. 이 부분을 order로 조절해 준 이유는 다른 상자에 있어서 영향을 주지 않는데 배열 상에는 붙어 있기 때문에 영향을 준다고 계산되는 경우가 생기기 때문이다.

위 아래, 즉 3차원에 대한 부분은 어차피 nr nc 구할때 값은 정해지니까 배열의 크기를 넘는지만 체크했다. 

 

완성된 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main_BOJ_7569_토마토 {
	/*
	 * 704ms
	 */
	
	static int[][] tomato;

	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());

		tomato = new int[N * H][M];

		for (int i = 0; i < N * H; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < M; j++) {
				tomato[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		int day = 0;

		Queue<int[]> queue = new LinkedList<int[]>();

		for (int i = 0; i < N * H; i++) {
			for (int j = 0; j < M; j++) {
				if (tomato[i][j] == 1) {
					queue.offer(new int[] { i, j, 0 });
				}
			}
		}
		
		if (queue.size() == 0) {
			System.out.println(-1);
			System.exit(0);
		}

		// 위 아래 추가
		int[] dr = { -1, 1, 0, 0, -N, N };
		int[] dc = { 0, 0, -1, 1, 0, 0 };

		while (queue.size() > 0) {
			int[] current = queue.poll();
			day = current[2];
			int order = current[0] / N; // 몇번째 상자인지
			for (int p = 0; p < 6; p++) {
				int nr = current[0] + dr[p];
				int nc = current[1] + dc[p];
				if (p == 4 || p == 5) { // 위아래는 따로 인덱스 관리해줌
					if (nr >= 0 && nr < N * H && nc >= 0 && nc < M) {
						if (tomato[nr][nc] == 0) {
							queue.offer(new int[] { nr, nc, day + 1 });
							tomato[nr][nc] = 1;
						}
					}
				}
				if (nr >= order * N && nr < (order + 1) * N && nc >= 0 && nc < M) { // 박스 안에서 인덱스 관리해줌
					if (tomato[nr][nc] == 0) {
						queue.offer(new int[] { nr, nc, day + 1 });
						tomato[nr][nc] = 1;
					}
				}
			}
		}

		boolean flag = true;

		as: for (int i = 0; i < N * H; i++) {
			for (int j = 0; j < M; j++) {
				if (tomato[i][j] == 0) {
					flag = false;
					break as;
				}
			}
		}

		if (flag)
			System.out.println(day);
		else
			System.out.println(-1);
	} // end of main
}