[JVAV] BOJ(백준) - 토마토 - 7569

- 문제 내용

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

7569번: 토마토

 

---

- 문제 접근 방법

이문제는 전에 풀었던 토마토(7576) 문제와 그냥 똑같은 풀이방법으로 푼다고 생각하면된다.

하나 다른점은 토마토박스가 3차원배열로 돼있고 상하좌우 뿐만아니라 위아래의 경우도 생각해야 한다는점만 다르다.

이말은 토마토박스를 3차원 배열로 받고 위아래 경우를 어떻게 처리할지만 알면 바로 풀수 있다는 말이다.

 

위아래의 경우는 단순히 상하좌우처럼 위아래의 값을 변화시킬 수 있는 배열을 하나 만들어주면된다.

그렇게하면 풀이방법은 바로전 토마토 문제와 동일하게

 

1. 큐에 현재 익은 토마토의 위치값을 저장한 객체를 넣어준다.

2. 큐의 객체를 반환해서 상하좌우 위아래를 돌고 조건에 맞다면 0이었던 토마토를 현재 갖고 있는 바로직전의 토마토+1을 해준다.

3. +1해준 토마토의 위치값을 다시 큐에 넣어준다

4. 1~3을 큐가 빌때까지 반복한다.

5. 최대일수를 구해준다.

 

이렇게 해주면된다.

 

---

- 풀이

 

위치 저장할 클래스

class PointZXY{//높이,가로,세로 위치 저장할 클래스
	int pointX;
	int pointY;
	int pointZ;
	
	public PointZXY(int z, int x, int y) {
		this.pointX = x;
		this.pointY = y;
		this.pointZ = z;
	}
}

 

BFS

public void solution() {//bfs 
		Queue<PointZXY> queue = new LinkedList<PointZXY>();
		
		for(int i=0; i<H; i++) {
			for(int j=0; j<N; j++) {
				for(int k=0; k<M; k++) {
					if(tomato[i][j][k]==1) {
						queue.add(new PointZXY(i, j, k));//높이(면,H), 행(세로크기,N), 열(가로크기,M)
					}
				}
			}
		}
		
		while(!queue.isEmpty()) {
			PointZXY point = queue.poll();
			int nowX = point.pointX;
			int nowY = point.pointY;
			int nowZ = point.pointZ;
			
			for(int i=0; i<6; i++) {//상하좌우 위아래 경우하나씩 돌리기.
				int dx = nowX + x[i];
				int dy = nowY + y[i];
				int dz = nowZ + z[i];
				
				if(dx>=0 && dy>=0 && dz>=0 && dx<N && dy<M && dz<H) {//다음 인덱스는 이조건을 만족해야함.
					if(tomato[dz][dx][dy]==0) {
						tomato[dz][dx][dy]=tomato[nowZ][nowX][nowY]+1;
						queue.add(new PointZXY(dz, dx, dy));
					}//if
				}//if
			}//for
		}//while
		
		for(int i=0; i<H; i++) {
			for(int j=0; j<N; j++) {
				for(int k=0; k<M; k++) {
					if(tomato[i][j][k]==0) {//토마토가 다익지 않았을때
						MAX=-1;
						return;
					}//if
					MAX = Math.max(tomato[i][j][k], MAX); //최대 일수 비교
				}//for
			}//for
		}//for
		
		MAX -= 1; //첫 시작이 익은 토마토 즉, 1일때 시작하기 때문에 마지막 일수에 1을 빼줘야 값이 나옴.
	}//solution

---

전체코드

package org.boj.dfs.bfs;

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 BOJ_7569 {
	static int M,N,H; //열(가로크기), 행(세로크기), 높이
	static int[][][] tomato;
	static int[] x = {0, 0, -1, 1, 0, 0}; //상하좌우(가로)
	static int[] y = {-1, 1, 0, 0, 0, 0}; //상하좌우(세로)
	static int[] z = {0, 0, 0, 0, -1, 1}; //위아래(높이)
	
	static int MAX=Integer.MIN_VALUE; //최대 일수
	
	public void solution() {//bfs 
		Queue<PointZXY> queue = new LinkedList<PointZXY>();
		
		for(int i=0; i<H; i++) {
			for(int j=0; j<N; j++) {
				for(int k=0; k<M; k++) {
					if(tomato[i][j][k]==1) {
						queue.add(new PointZXY(i, j, k));//높이(면,H), 행(세로크기,N), 열(가로크기,M)
					}
				}
			}
		}
		
		while(!queue.isEmpty()) {
			PointZXY point = queue.poll();
			int nowX = point.pointX;
			int nowY = point.pointY;
			int nowZ = point.pointZ;
			
			for(int i=0; i<6; i++) {//상하좌우 위아래 경우하나씩 돌리기.
				int dx = nowX + x[i];
				int dy = nowY + y[i];
				int dz = nowZ + z[i];
				
				if(dx>=0 && dy>=0 && dz>=0 && dx<N && dy<M && dz<H) {//다음 인덱스는 이조건을 만족해야함.
					if(tomato[dz][dx][dy]==0) {
						tomato[dz][dx][dy]=tomato[nowZ][nowX][nowY]+1;
						queue.add(new PointZXY(dz, dx, dy));
					}//if
				}//if
			}//for
		}//while
		
		for(int i=0; i<H; i++) {
			for(int j=0; j<N; j++) {
				for(int k=0; k<M; k++) {
					if(tomato[i][j][k]==0) {//토마토가 다익지 않았을때
						MAX=-1;
						return;
					}//if
					MAX = Math.max(tomato[i][j][k], MAX); //최대 일수 비교
				}//for
			}//for
		}//for
		
		MAX -= 1; //첫 시작이 익은 토마토 즉, 1일때 시작하기 때문에 마지막 일수에 1을 빼줘야 값이 나옴.
	}//solution
	
	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());
		
		tomato = new int[H][N][M];
		for(int i=0; i<H; i++) {
			for(int j=0; j<N; j++) {
				st = new StringTokenizer(br.readLine());
				for(int k=0; k<M; k++) {
					tomato[i][j][k]=Integer.parseInt(st.nextToken());
				}
			}
		}
		
		new BOJ_7569().solution();
		System.out.println(MAX);
	}
}

class PointZXY{//높이,가로,세로 위치 저장할 클래스
	int pointX;
	int pointY;
	int pointZ;
	
	public PointZXY(int z, int x, int y) {
		this.pointX = x;
		this.pointY = y;
		this.pointZ = z;
	}
}

 

---

- 마치며

전 토마토문제와 다르게 방문배열은 딱히 쓸때가 없기때문에 제외했고 그외에 풀이 방법은 똑같다.