[백준(Baekjoon)][자바(java)] 7579 : 토마토 / 그래프와 순회

 

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

7579번: 앱

 

문제 풀이

 

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 {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int M = Integer.parseInt(st.nextToken()),
			N = Integer.parseInt(st.nextToken()),
			H = Integer.parseInt(st.nextToken()),
			map[][][] = new int[H][N][M], val, i, j, k,
			cnt_total = H * N * M;
		boolean visited[][][] = new boolean[H][N][M];
		Queue<int[]> queue = new LinkedList<>(); // h(height), x, y, d(distance)
		for (k = 0; k < H; ++k) {
			for (i = 0; i < N; ++i) {
				st = new StringTokenizer(br.readLine());
				for (j = 0; j < M; ++j) {
					val = Integer.parseInt(st.nextToken());
					map[k][i][j] = val;
					if (val == 1) {
						visited[k][i][j] = true;
						queue.add(new int[]{k, i, j, 0});
					}
					if (val == -1)
						cnt_total--;
				}
			}
		}
		br.close();
		
		cnt_total -= queue.size();

		final int dx[] = {0, 0, 1, -1, 0, 0}, dy[] = {1, -1, 0, 0, 0, 0}, 
			dh[] = {0, 0, 0, 0, 1, -1}, n = dx.length;
		int cnt = 0, pos[], h, x, y, d, nh, nx, ny, nd, answer = 0;
		loop:
		while (!queue.isEmpty()) {
			pos = queue.remove();
			h = pos[0];
			x = pos[1];
			y = pos[2];
			d = pos[3];
			nd = d + 1;
			for (i = 0; i < n; ++i) {
				nh = h + dh[i];
				nx = x + dx[i];
				ny = y + dy[i];
				if (nh < 0 || nh >= H || nx < 0 || nx >= N || ny < 0 || ny >= M || 
					visited[nh][nx][ny] || map[nh][nx][ny] == -1)
					continue;
				cnt++;
				if (cnt == cnt_total) {
					answer = nd;
					break loop;
				}
				map[nh][nx][ny] = 1;
				visited[nh][nx][ny] = true;
				queue.add(new int[]{nh, nx, ny, nd});
			}
		}

		System.out.println(cnt == cnt_total ? answer : -1);
	}
}