[백준/자바] 7569번: 토마토

문제

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

풀이

• 토마토는 아래의 그림과 같이 격자모양 상자의 칸에 하나씩 넣은 다음, 상자들을 수직으로 쌓아 올려 보관 중이다.
  
• 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익게 된다.
• 토마토의 인접한 곳은 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향에 있는 토마토를 의미한다.
• 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지 최소 일수 출력

시작점이 여러 개인 멀티 소스 BFS 문제 입니다.
순회를 하다가 토마토를 발견하면 탐색을 시작하는 것이 아닌, 시작할 수 있는 모든 좌표에서 동시 다발적으로 탐색을 시작해야 합니다.

		for (int k = 0; k < o; k++) {
			for (int i = 0; i < n; i++) {
				st = new StringTokenizer(br.readLine());
				for (int j = 0; j < m; j++) {
					graph[i][j][k] = Integer.parseInt(st.nextToken());
					if (graph[i][j][k] == 1) {
						queue.add(new int[] { i, j, k });
						visited[i][j][k] = 0;
					}
				}
			}
		}

• 그러기 위해서 queue를 전역 변수로 설정하고 익은 토마토(1)인 경우에 바로 queue에 넣어 주었습니다.

	private static void bfs() {
		while (!queue.isEmpty()) {
			int[] cur = queue.poll();
			int r = cur[0], c = cur[1], h = cur[2];
			
			for (int i = 0; i < 6; i++) {
				int nr = r + dr[i];
				int nc = c + dc[i];
				int nh = h + dh[i];
				
				if (nr < 0 || nr >= n || nc < 0 || nc >= m || nh < 0 || nh >= o) continue;
				if (graph[nr][nc][nh] == -1 || visited[nr][nc][nh] != -1) continue;
				
				queue.add(new int[] { nr, nc, nh });
				visited[nr][nc][nh] = visited[r][c][h] + 1;
			}
		}
		
	}

• 모든 시작점이 정해졌다면, 모든 시작점 좌표들을 탐색하기 시작합니다.
• 6방 탐색을 통해 '범위가 벗어나지 않았는지?, 빈칸이 아닌지?, 방문하지 않은 좌표인지?' 확인을 하고 조건에 만족하다면 다음 좌표를 queue에 담고 연쇄적으로 탐색을 합니다.

	private static void computeAnswer() {
		answer = 0;
		for (int k = 0; k < o; k++) {
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < m; j++) {
					if (graph[i][j][k] != -1 && visited[i][j][k] == -1) {
						answer = -1;
						return;
					}
					if (visited[i][j][k] > answer) answer = visited[i][j][k];
				}
			}
		}
	}

• 만약 익지 않은 토마토가 있다면 정답을 -1로 설정 후 리턴하였습니다.

코드

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

public class Main_7569 {
	static int n, m, o, answer;
	static int[][][] graph, visited;
	
	static Queue<int[]> queue = new ArrayDeque<>();
	
	static final int[] dr = { -1, 1, 0, 0, 0, 0 };
	static final int[] dc = { 0, 0, -1, 1, 0, 0 };
	static final int[] dh = { 0, 0, 0, 0, -1, 1 };
	
    // 토마토 상자와 최소 일수를 찾을 상자 초기화
	private static void init() {
		graph = new int[n][m][o];
		visited = new int[n][m][o];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				Arrays.fill(visited[i][j], -1);
			}
		}
	}
	
    // BFS
	private static void bfs() {
		while (!queue.isEmpty()) {
			int[] cur = queue.poll();
			int r = cur[0], c = cur[1], h = cur[2];
			
			for (int i = 0; i < 6; i++) {
				int nr = r + dr[i];
				int nc = c + dc[i];
				int nh = h + dh[i];
				
				if (nr < 0 || nr >= n || nc < 0 || nc >= m || nh < 0 || nh >= o) continue;
				if (graph[nr][nc][nh] == -1 || visited[nr][nc][nh] != -1) continue;
				
				queue.add(new int[] { nr, nc, nh });
				visited[nr][nc][nh] = visited[r][c][h] + 1;
			}
		}
		
	}
	
    // 정답을 갱신하는 메서드
	private static void computeAnswer() {
		answer = 0;
		for (int k = 0; k < o; k++) {
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < m; j++) {
					if (graph[i][j][k] != -1 && visited[i][j][k] == -1) {
						answer = -1;
						return;
					}
					if (visited[i][j][k] > answer) answer = visited[i][j][k];
				}
			}
		}
	}
	
	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());
		o = Integer.parseInt(st.nextToken());
		
		init();
		
		for (int k = 0; k < o; k++) {
			for (int i = 0; i < n; i++) {
				st = new StringTokenizer(br.readLine());
				for (int j = 0; j < m; j++) {
					graph[i][j][k] = Integer.parseInt(st.nextToken());
					if (graph[i][j][k] == 1) {
						queue.add(new int[] { i, j, k });
						visited[i][j][k] = 0;
					}
				}
			}
		}
		
		bfs();
		computeAnswer();
		
		System.out.println(answer);
	}

}