[백준알고리즘-JAVA]7569번 풀이(토마토3) - 초보도 이해하는 풀이

안녕하세요

인포돈 입니다.

백준 알고리즘 7569번 풀이입니다. 

* 참고사항
 - 개발환경은 eclipse을 기준으로 작성되었습니다.
 - java언어를 이용하여 문제를 풀이합니다.
 - 알고리즘 문제는 풀이를 보고 해답을 찾는 것도 중요하지만 무엇보다 스스로 풀이를 시도해봐야 합니다!!
(해당 풀이를 보기 전 충분히 문제에 대해 고민해봐야 합니다!)
 - 해당 풀이 말고도 수많은 풀이 방법이 존재합니다.

---

백준 7569 (토마토 3)

문제

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

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

 

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

입력

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

 

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

출력

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

public class Main {

	static boolean[][][] check;
	static int[][][] arr;
	static int[] moveX = {0, 0, 1, -1, 0, 0};
	static int[] moveY = {1, -1, 0, 0, 0, 0};
	static int[] moveZ = {0, 0, 0, 0, 1, -1};
	static int N, M, H, ans=0;
	static StringBuilder sb = new StringBuilder();
	
	static Queue<tomato> q = new LinkedList<>();

	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][N][M];
		check = new boolean[H][N][M];
		
		for(int i = 0 ; i < H ; i++ ) {
			for(int j = 0 ; j < N ; j++) {
				StringTokenizer str = new StringTokenizer(br.readLine());
				for(int z = 0 ; str.hasMoreTokens() ; z++) {
					arr[i][j][z] = Integer.parseInt(str.nextToken());
					if(arr[i][j][z] == 1)
						q.add(new tomato(i,j,z));
				}
			}
		}
		
		bfs();

		loop : for(int i = 0 ; i < H ; i++ ) {;
			for(int j = 0 ; j < N ; j++) {
				for(int z = 0 ; z < M ; z++) {
					if(arr[i][j][z] == 0) {
						ans = 0;
						break loop;
					}
					ans = Math.max(ans, arr[i][j][z]);
				}
			}
		}
		
		System.out.println(ans-1);
		}

	public static void bfs() {

		while(!q.isEmpty()) {
			tomato t = q.poll();
			check[t.z][t.x][t.y] = true;
			
			for(int i = 0 ; i < 6 ; i++) {
				int nextX = t.x + moveX[i];
				int nextY = t.y + moveY[i];
				int nextZ = t.z + moveZ[i];
				
				if(nextX < 0 || nextY < 0 || nextZ < 0 ||
						nextX >= N || nextY >= M || nextZ >= H)
					continue;
				
				if(check[nextZ][nextX][nextY] || arr[nextZ][nextX][nextY] == -1
						|| arr[nextZ][nextX][nextY] ==1)
					continue;
				
				q.add(new tomato(nextZ,nextX,nextY));
				
				arr[nextZ][nextX][nextY] = arr[t.z][t.x][t.y]+ 1;
				
				check[nextZ][nextX][nextY] = true;
				
			}
		}
	}

}


class tomato{
	int x;
	int y;
	int z;
	
	public tomato(int z, int x, int y) {
		this.z = z;
		this.x = x;
		this.y = y;
	}
}

네 보시다시피 코드가 굉장히 길게 되어 있는데요 사실 이전 토마토 문제를 풀어봤더라면 아주 쉽게 풀이할 수 있었던 알고리즘이었습니다. 해당 알고리즘에서의 핵심은 바로 bfs의 구현이 핵심이 되겠죠. 뭐 크게 어려울 게 없으니 알고리즘 흐름도를 보고 전체적인 흐름을 생각하면서 STEP을 따라가 보면서 이해해보죠

---

알고리즘 흐름도

 입력받기 -> 3차원 배열 초기화하기 -> 큐에 1 값이 있는 좌표 저장하기 -> 해당 큐에서 하나씩 꺼내서 조건을 만족하면 해당 큐의 값 +1 하기 -> 3차원 배열을 순회하면서 값이 0이면 -1 출력 아니라면 최댓값 출력

---

STEP1 3차원 배열 초기화 및 큐에 좌표 저장하기

		arr = new int[H][N][M];
		check = new boolean[H][N][M];
		
		for(int i = 0 ; i < H ; i++ ) {
			for(int j = 0 ; j < N ; j++) {
				StringTokenizer str = new StringTokenizer(br.readLine());
				for(int z = 0 ; str.hasMoreTokens() ; z++) {
					arr[i][j][z] = Integer.parseInt(str.nextToken());
					if(arr[i][j][z] == 1)
						q.add(new tomato(i,j,z));
				}
			}
		}

arr 배열은 문제에서 주어진 -1, 0 1을 저장하는 배열입니다.

check배열은 방문했음을 알려주는 배열입니다.

3중 for문을 활용해서 입력받은 값들을 arr에 저장하고 만약 해당 값에 1이 저장되어있다면 q에 저장해 줍니다.

 

여기서 new tomato는 아래와 같습니다.

class tomato{
	int x;
	int y;
	int z;
	
	public tomato(int z, int x, int y) {
		this.z = z;
		this.x = x;
		this.y = y;
	}
}

뭐 크게 어려울 게 없고 x, y, z좌표를 담고 있는 tomato의 위치를 표시하기 위한 class입니다. 오브젝트를 활용해서 하나의 값이 아니라 여러의 값을 저장할 수 있죠

---

STEP2 bfs 구현하기 (조건을 만족하면 해당 큐 값의 +1 하기)

	public static void bfs() {
		while(!q.isEmpty()) {
			tomato t = q.poll();
			check[t.z][t.x][t.y] = true;
			
			for(int i = 0 ; i < 6 ; i++) {
				int nextX = t.x + moveX[i];
				int nextY = t.y + moveY[i];
				int nextZ = t.z + moveZ[i];
				
				if(nextX < 0 || nextY < 0 || nextZ < 0 ||
						nextX >= N || nextY >= M || nextZ >= H)
					continue;
				
				if(check[nextZ][nextX][nextY] || arr[nextZ][nextX][nextY] == -1
						|| arr[nextZ][nextX][nextY] ==1)
					continue;
				
				q.add(new tomato(nextZ,nextX,nextY));
				
				arr[nextZ][nextX][nextY] = arr[t.z][t.x][t.y]+ 1;
				
				check[nextZ][nextX][nextY] = true;
				
			}
		}
	}

일반적인 bfs의 형태를 보이죠 앞서서 arr배열을 초기화할 때 q에 해당 값을 넣어주었죠? 이에 따라서 q에는 1을 값을 가진 토마토의 좌표를 가지고 있죠. 이제 여기서 해당 좌표를 하나씩 꺼냅니다. (물론 FIFO 먼저 들어간 것 먼 저죠)

 

해당 값을 뽑아내고 해당 값을 방문했음을 CHECK배열에 넣어줍니다.

 

6번을 반복합니다. (왜냐? 상하좌우 앞뒤를 순회해야 하기 때문입니다.)

이제 좌표를 상 하 좌 우 앞 뒤를 순회합니다.

첫 번째 조건문 - 해당 좌표(상 하 좌 우 앞 뒤)가 배열의 범위를 넘어가면 다른 방향으로 가라

두 번째 조건문 - 해당 좌표(상 하 좌 우 앞 뒤)가 이미 방문했거나, 값이 -1이거나 1이라면 다른 방향으로 가라

(1이라면 이미 Q에 들어가 있기 때문입니다.)

 

이제 해당 조건문을 통과하였다면, Q에 해당 값을 추가해 줍니다. 또한 해당 ARR배열에 해당 좌표에 이전 좌표의 값 +1을 해줍니다. (이 의미는 토마토가 익어가는 날입니다. 즉, 이전보다 1일 더 후에 익는다는 의미)

마지막으로 해당 좌표를 방문했다고 표시합니다.

 

이를 반복적으로 한다면, 모든 ARR배열에 값이 할당될 것입니다.

---

STEP 3 3차원 배열 순회하며 값 비교하기

		loop : for(int i = 0 ; i < H ; i++ ) {;
			for(int j = 0 ; j < N ; j++) {
				for(int z = 0 ; z < M ; z++) {
					if(arr[i][j][z] == 0) {
						ans = 0;
						break loop;
					}
					ans = Math.max(ans, arr[i][j][z]);
				}
			}
		}
		
		System.out.println(ans-1);

간단한 3차원 배열을 순회합니다 3개의 반복문 돌리면서 해당 값이 하나라도 0이 있으면, -1로 인해 갈 수 없었던 곳을 의미하죠. 바로 -1을 출력해 주면 됩니다. 그게 아니라면 정답 ans변수에 해당 값이랑 비교해서 큰 값을 넣어줍니다.

 

결국에 가장 큰 값이 마지막 토마토가 익는 날이 되겠습니다.