[BJ7569] 토마토

 백준 - 토마토 

문제 링크

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

7569번: 토마토

 

문제 입출력

5 3 1
0 -1 0 0 0
-1 -1 0 1 1
0 0 0 1 1

-1

 

문제 풀이

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;


public class Main {
	static int ans, M, N, H;
	static int[][][] map;

	static int[] dh = { 0, 0, 0, 0, 1, -1 };
	static int[] dy = { -1, 1, 0, 0, 0, 0 };
	static int[] dx = { 0, 0, -1, 1, 0, 0 };

	static Queue<Node> q = new ArrayDeque<>();


	public static void main(String[] args) throws Exception {
		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());

		// 초기화
		map = new int[H][N][M];
		q.clear();
		ans = Integer.MIN_VALUE;

		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++) {
					int m = Integer.parseInt(st.nextToken());
					map[k][i][j] = m;

					if (m == 1) q.offer(new Node(k, i, j, 0));
				}

			}

		}

		// 탐색
		bfs();

		// 출력
		if (check()) ans = -1;
		System.out.println(ans);
	} // end main


	private static void bfs() {
		while (!q.isEmpty()) {
			Node node = q.poll();
			int h = node.h;
			int y = node.y;
			int x = node.x;

			ans = Math.max(ans, node.d);

			for (int d = 0; d < 6; d++) {
				int nh = h + dh[d];
				int ny = y + dy[d];
				int nx = x + dx[d];

				if (nh < 0 || nh >= H) continue;
				if (ny < 0 || ny >= N || nx < 0 || nx >= M) continue;
				if (map[nh][ny][nx] == 1) continue;
				if (map[nh][ny][nx] == -1) continue;

				q.offer(new Node(nh, ny, nx, node.d + 1));
				map[nh][ny][nx] = 1;
			}

		}

	} // end bfs


	private static boolean check() {
		for (int h = 0; h < H; h++) {
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) if (map[h][i][j] == 0) return true;
			}

		}

		return false;

	}


	static class Node {
		int h, y, x;
		int d;


		public Node(int h, int y, int x, int d) {
			this.h = h;
			this.y = y;
			this.x = x;
			this.d = d;
		}


		@Override
		public String toString() {
			return "Node [y=" + y + ", x=" + x + ", d=" + d + "]";
		}

	}
}

2022.09.19 - [✏️ 𝗔𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺/백준 알고리즘] - [BJ7576] 토마토

[BJ7576] 토마토

• bfs 로 풀 수 있는 문제 입니다.
• Node 를 생성하여 depth 를 카운팅합니다.

 

 

 

 

 

 

 

 

# 백준 토마토 자바 # 백준 토마토 java # 백준 토마토 BJ7576

---