[Baekjoon] 백준 7569 토마토 (G5^ / BFS) - Java

링크

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

7569번: 토마토

 

 

 

 

문제 해석

1 : 익은 토마토

0 : 익지 않은 토마토

-1 : 빈 칸 (벽)

 

익은 토마토는 인접한 토마토에 영향을 미침

 

토마토들이 모두 익는데 걸리는 시간을 구하기

 

 

입력

첫 번쨰 줄 : M N H

  M : 상자의 가로 칸 수

  N : 상자의 세로 칸 수

  H : 상자의 수

 

나머지 줄 : 차례대로 각 박스에 토마토 위치를 한줄씩 입력

 

 

 

출력

토마토가 모두 익는데 걸리는 시간을 출력

단, 익지 못하는 토마토가 있다면 -1을 결과로 출력

 

 

 

 

풀이 & 코드 해석

이전 토마토 문제를 풀어보았다면 조금만 더 생각해보았을 때 해결 가능합니다.

 

https://angelplayer.tistory.com/408

[Baekjoon] 백준 7576 토마토 (G5^ / BFS) - Java

 

 

 

기존에 풀었던 7576 토마토와 다른 점은 박스가 추가되어 토마토 상자가 위 아래로 겹쳐져 있다는 점입니다.

 

따라서 사방탐색 이외에도 위아래로 탐색이 필요하며, 이를 nr, nc, nh에 추가적으로 구현하였습니다.

 

이외로는 Queue에 offer하는 조건이 추가 된 점말고는 크게 달라진 점이 없습니다.

 

 

 

 

코드

import java.io.*;
import java.util.*;

public class Main {
	static int[][][] map;
	
	static int[] nr = {-1, 0, 1, 0, 0, 0};
	static int[] nc = {0, 1, 0, -1, 0, 0};
	static int[] nh = {0, 0, 0, 0, 1, -1};
	
	static class Point {
		int h;
		int r;
		int c;
		int level;
		
		Point (int h, int r, int c, int level) {
			this.h = h;
			this.r = r;
			this.c = c;
			this.level = level;
		}
	}
	
	static int answer = 0;
	static Queue<Point> q = new LinkedList<>();  
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		st = new StringTokenizer(br.readLine());
		
		int M = Integer.parseInt(st.nextToken()); // 가로 칸 수
		int N = Integer.parseInt(st.nextToken()); // 세로 칸 수
		int H = Integer.parseInt(st.nextToken()); // 쌓아진 상자 수
		
		map = new int[H][N][M];
		int zeroCnt = 0;
		
		// 입력
		for (int k = 0; k < H; k++) {
			for (int i = 0; i < N; i++) {
				st = new StringTokenizer(br.readLine());
				
				for (int j = 0; j < M; j++) {
					map[k][i][j] = Integer.parseInt(st.nextToken());
					if (map[k][i][j] == 1) {
						zeroCnt++;
					}
				}
			}
		}

		
//		print();
		
		// Queue에 저장
		for (int k = 0; k < map.length; k++) {
			for (int i = 0; i < map[0].length; i++) {				
				for (int j = 0; j < map[0][0].length; j++) {
					if (map[k][i][j] == 1) {
						q.offer(new Point(k, i, j, 0));
					}
				}
			}
		}
		
		bfs();
		
		for (int k = 0; k < map.length; k++) {
			for (int i = 0; i < map[0].length; i++) {				
				for (int j = 0; j < map[0][0].length; j++) {
					if (map[k][i][j] == 0) {
						System.out.println(-1);
						return;
					}
				}
			}
		}
		
		System.out.println(answer);
		
	} // [E] Main

	
	static void bfs() {
		while(!q.isEmpty()) {
			Point p = q.poll();
			
			for (int d = 0; d < nr.length; d++) {
				int dr = p.r + nr[d];
				int dc = p.c + nc[d];
				int dh = p.h + nh[d];
				
				if (dh >= 0 && dh < map.length && dr >= 0 && dr < map[0].length &&
						dc >= 0 && dc < map[0][0].length && map[dh][dr][dc] == 0) {
					q.offer(new Point(dh, dr, dc, p.level + 1));
					map[dh][dr][dc] = 1;
					answer = p.level + 1;
				}
			}
		}
	}
	
	static void print() {
		for (int k = 0; k < map.length; k++) {
			for (int i = 0; i < map[0].length; i++) {
				
				for (int j = 0; j < map[0][0].length; j++) {
					System.out.print(map[k][i][j]);
				}
				System.out.println();
			}
			System.out.println();
		}
	}
}

 

 

 

 

발생한 문제 & 해결 방안

처음에는 bfs를 두 개를 돌릴까 고민했지만 비효율적일 것 같아서 하나로 변경하였고, 제대로 동작하였다.

 

 

 

 

 

 

 

해당 코드는 에디터가 코드 연습을 위해 직접 작성하였습니다.

혹시 오류가 있거나 더 좋은 코드 방향성을 아시는 분은 댓글로 남겨주시면 감사하겠습니다!

python source : https://github.com/ssh5212/conding-test-practice

java source : https://github.com/ssh5212/coding-test-java