[Baekjoon/Java] 7569번 토마토

문제

철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자모양 상자의 칸에 하나씩 넣은 다음, 상자들을 수직으로 쌓아 올려서 창고에 보관한다.

창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토에 인접한 곳은 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지 그 최소 일수를 알고 싶어 한다.

토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.

 

입력

첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, 1 ≤ H ≤ 100 이다. 둘째 줄부터는 가장 밑의 상자부터 가장 위의 상자까지에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 하나의 상자에 담긴 토마토의 정보가 주어진다. 각 줄에는 상자 가로줄에 들어있는 토마토들의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0 은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다. 이러한 N개의 줄이 H번 반복하여 주어진다.

토마토가 하나 이상 있는 경우만 입력으로 주어진다.

 

출력

여러분은 토마토가 모두 익을 때까지 최소 며칠이 걸리는지를 계산해서 출력해야 한다. 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.

 

문제 풀이

첫번째 풀이 - 시간 초과

토마토가 있는 부분을 List 배열에 넣고 bfs를 돌려 상하좌우를 탐색하고 3차원이기 때문에 위, 아래도 따로 탐색을 진행했다. 아! 나는 3차원 배열이지만 2차원으로 풀었다. 근데 시간 초과가 나서 List 배열에 넣지 않고 바로 Queue에 넣었다.(이게 원인이 아닐 것이라는건 어느정도 예측했지만 ....) 그래도 시간 초과가 났다.

 

두번째 풀이 - 틀렸습니다

시간 초과 풀이에서는 상하좌우랑 위,아래를 따로 탐색하도록 했었다.

델타배열을 int [] dx = {-1, 0, 1, 0}; int [] dy = {0, 1, 0, -1}; 로만 두고 반복문을 돌리고 나머지를 구해서 현재 x 좌표와 같을 때만 탐색을 하도록 !

이 부분은 상하좌우위아래를 한 번에 탐색할 수 있도록 int [] dx = {N, -N, -1, 0, 1, 0}; int [] dy = {0, 0, 0, 1, 0, -1}; 로 바꿔서 풀었는데 틀렸다. 질문 게시판에 반례를 찾아서 해봤는데 안 되는 케이스가 하나 있었다.

2 2 2

1 -1

0  0

-1 0

-1 0

답은 4인데 자꾸 3으로 나왔다. 아무리 생각해도 현재 로직에서 틀린게 없어보여서 이 부분을 해결하는데만 1시간이 걸렸다.

원인은 2차원 배열로 놓고 푼다면 1,1 인 상태에서 원래는 3,1 로 갔다가 3,1 에서 2,1을 방문해야하는건데 1,1에서 3,1과 2,1을 모두 방문하는 것이었다.

직접 그려보니 1,1인 상태에서 델타배열에 의해 2,1에 방문하는 것이었다. 하지만 1,1 기준 2,1은 상하좌우위아래에 위치해있지 않다. 다만 2차원 배열로 두면 층 구분이 되지 않기 때문에 1,1 아래에 2,1이 위치하게 되는 반례가 존재하는 것이었다. 내가 나름 생각한대로 이 조건을 무시하기 위한 조건을 짰지만 안 됐고 결국 3차원 배열로 바꿔서 풀었다.

 

최종 풀이

3차원 배열로 풀 때 제일 조심해야할 것은 반복문을 돌릴 때 높이(H)가 가장 바깥 반복문에 위치해야한다. 델타배열도 3개로 만들어줬다. 나머지는 원래 bfs 풀 때랑 동일하다.

 

코드

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

public class Main {
	static int M;
	static int N; 
	static int H;
	static int[][][] tomato;
	static boolean[][][] visited;
	static Queue<Node> queue = new LinkedList<Node>();
	static int[] dx;
	static int[] dy;
	static int[] dh;
	static int days = 0;
	
	public static class Node{
		int h;
		int x;
		int y;
		int day;
		
		public Node(int h, int x, int y, int day) {
			this.h = h;
			this.x = x;
			this.y = y;
			this.day = day;
		}
	}
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		Scanner sc = new Scanner(System.in);
		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());
		
		dx = new int[]{0, 0, -1,0,1,0};
		dy = new int[]{0, 0, 0,1,0,-1};
		dh = new int[] {1,-1,0,0,0,0};
		
		tomato = new int[H][N][M];
		visited = new boolean[H][N][M];
		for(int h=0; h<H; h++) {
			for(int i=0; i<N; i++) {
				st = new StringTokenizer(br.readLine());
				for(int j=0; j<M; j++) {
					int num = Integer.parseInt(st.nextToken());
					tomato[h][i][j] = num;
					
					if(num == 1) {
						queue.add(new Node(h,i,j,0));
						visited[h][i][j] = true;
					}
				}
				
			}
		}
		
		bfs();
		
		boolean isTomato = true;
		for(int i=0; i<H; i++) {
			for(int j=0; j<N; j++) {
				for(int h=0; h<M; h++) {
					if(tomato[i][j][h] == 0) {
						isTomato = false;
						break;
					}
				}
				
			}
		}
		
		if(isTomato) {
			System.out.println(days);
		}else {
			System.out.println(-1);
		}
		
	}
	private static void bfs() {
		while(!queue.isEmpty()) {
			Node node = queue.remove();
			
			for(int d=0; d<6; d++) {
				int nx = dx[d] + node.x;
				int ny = dy[d] + node.y;
				int nh = dh[d] + node.h;
				
				if(0<=nx && nx<N && 0<=ny && ny<M && 0<=nh && nh<H) {
					if(tomato[nh][nx][ny] == 0 && !visited[nh][nx][ny]) {
						
						tomato[nh][nx][ny] = 1;
						visited[nh][nx][ny] = true;
						queue.add(new Node(nh, nx, ny, node.day+1));
						days = Math.max(days, node.day+1);
					}
				}
			}
		}
		
	}
}

새롭게 알게 된 점 & 느낀점

2차원 배열로 풀어보고싶었는데 풀지 못 해서 아쉽다. 3차원 배열로는 거의 처음 풀어보는거라 생소했는데 2차원 배열이랑 거의 비슷해서 앞으로 거부감 없이 풀 수 있을 것 같다.

 

 

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

7569번: 토마토