쌉쌀한 무화과의 개발로그

[문제]

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

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

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

[입력]

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

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

[출력]

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

[예제]

>문제 풀이

 문제를 잘못 읽어서.. 진짜 한참을 헤맨 문제입니다....ㅎㅏ..

N x M 배열이 H번 반복되어 입력된다는 말을 똑같은 N x M 배열이 H번 쌓여져 있다고 해석해가지고..

(어쩐지..^^ 그렇게 토마토 박스 쌓을거면 2차원 배열 문제랑 뭐가 다른가 한참 생각했네요..쩝..)

문제를 제대로 해석한 후에는, mat[H][N][M] 3차원 배열과 visited[H][N][M] 3차원 배열을 이용해서 기존에 풀었던 토마토 문제(7576번)와 비슷하게 풀었습니다.

**입력

: N x M배열이 H번 반복되어 입력된다.

0: 익지 않은 토마토

1: 익은 토마토

-1: 빈 칸

*익은 토마토를 기준으로 상하좌우의 토마토들이 익어갑니다.

1.  0인 경우에 total++ 카운팅을 해줍니다.
   후에 cnt(0→1 익어간 토마토들 카운팅)와 비교해서 익지 않은 토마토가 남아있지 않은지 비교해주기 위함입니다.
2. 1인 경우 큐에 넣어줍니다. 저는 토마토의 위치정보를 Point(int h, int x, int y) 클래스에 담아서 큐에 넣었습니다.

**BFS

증감값은 dx={-1, 1, 0, 0, 0, 0}, dy={0, 0, -1, 1, 0, 0}, dh={0, 0, 0, 0, -1, 1} 배열로 선언해주었습니다.

그리고 큐.isEmpty 일 때 까지

h, x, y= q.poll();

nx=x+dx[i], ny=y+dy[i], nh= h+dh[i];

범위안에 들어오는 0≤nh≤H && 0≤nx≤N && 0≤ny≤M 에 대하여, 방문한적 없고 mat[][][]==0이면

- mat[nh][nx][ny] 방문 처리

- mat[nh][nx][ny]= mat[h][x][y]+1;

- max값 찾기 (날짜 카운팅을 위해서)

- 그리고 큐에 Point(nh, nx, ny)를 넣어주고

- cnt++; (total과 비교해서 0이었던 안익은 토마토들이 다 익었는지 비교하기 위한 변수cnt)

>전체 코드

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

public class Main {
	static int N, M, H, total, cnt=0, max=0;
	static int mat[][][];
	static boolean visited[][][];
	static Queue<Point> que;
	
	public static void main(String [] args) {
		Scanner scan= new Scanner(System.in);
		
		M= scan.nextInt();
		N= scan.nextInt();
		H= scan.nextInt();
		mat= new int[H][N][M];
		visited= new boolean[H][N][M];
		que= new LinkedList<Point>();
		
		//입력받기
		for(int i=0; i<H; i++) {
			for(int j=0; j<N; j++) {
				for(int k=0; k<M; k++) {
					mat[i][j][k]= scan.nextInt();
					if(mat[i][j][k]==1) que.offer(new Point(i,j,k));
					if(mat[i][j][k]==0) total++;
				}
			}
		}
		if(total==0) System.out.println("0");
		else bfs(0,0,0);
	}
	
	public static void bfs(int h, int x, int y) {
		int nx, ny, nh;
		Point p;
		int dh[]= {0, 0, 0, 0, -1, 1};
		int dx[]= {-1, 1, 0, 0, 0, 0};
		int dy[]= {0, 0, -1, 1, 0, 0};
		
		while(!que.isEmpty()) {
			p= que.poll();
			
			if(cnt==total) {
				System.out.println(max-1);
				return;
			}
			for(int i=0; i<6; i++) {
				nh= p.h+dh[i];
				nx= p.x+dx[i];
				ny= p.y+dy[i];
				
				if(nx<0||nx>=N||ny<0||ny>=M||nh<0||nh>=H) continue;
				
				if(mat[nh][nx][ny]==0&&!visited[nh][nx][ny]) {
					visited[nh][nx][ny]=true;
					mat[nh][nx][ny]= mat[p.h][p.x][p.y]+1;
					max=max>mat[nh][nx][ny]?max:mat[nh][nx][ny];
					que.offer(new Point(nh, nx, ny));
					cnt++;
				}
			}
			
		}//while
		System.out.println("-1");
	}//bfs
	
	static class Point {
		int x, y, h;
		
		public Point(int h, int x, int y) {
			this.h= h;
			this.x= x;
			this.y= y;
		}
	}
}

www.acmicpc.net/problem/7569