[Java] 백준(골드-5) 7569번 - 토마토
문제 풀이
이번 문제는 그래프 탐색인 BFS을 활용하는데, 3차원으로 접근하여 풀 수 있다.
아이디어 도출
BFS 문제는 2차원으로 탐색하는 것이 일반적인데, 이번 문제에서는 3차원으로 그래프 탐색을 진행해야 한다.
입력으로 주어지는 [H, N, M]을 [면(z), 열(x), 행(y)] 으로 생각하고 접근하면 쉽다.
이전에 풀었던 7576번 토마토 문제에서 3차원으로 접근하기만 하면 된다.
다음으로 문제 해결을 위해 생각해낸 아이디어는 다음과 같다.
- 면, 열, 행의 3차원 배열에 토마토 배열을 입력받고 그 중 익은 토마토의 위치를 큐에 담는다.
- BFS를 수행하며 6 방향(상, 하, 좌, 우, 위, 아래)으로 탐색을 하며 익지 않은 토마토가 있다면 깊이값으로 갱신해주고 큐에 삽입한다.
- BFS 탐색을 마친 후, 토마토 배열에 익지 않은 토마토가 하나라도 있다면 -1을 출력하고, 다 익었다면 깊이값을 출력한다.
여기서 6방향으로 탐색하기 위해 선언한 dx, dy, dz 배열을 유심히 기억해두자.
1
2
3
4
// 상, 하, 좌, 우, 위, 아래
static int[] dx = new int[]{0, 1, 0, -1, 0, 0};
static int[] dy = new int[]{1, 0, -1, 0, 0, 0};
static int[] dz = new int[]{0, 0, 0, 0, 1, -1};
문제 풀이를 위해 작성한 코드는 아래와 같다.
작성코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
import java.io.*;
import java.util.*;
class Main {
// 상, 하, 좌, 우, 위, 아래
static int[] dx = new int[]{0, 1, 0, -1, 0, 0};
static int[] dy = new int[]{1, 0, -1, 0, 0, 0};
static int[] dz = new int[]{0, 0, 0, 0, 1, -1};
// 열, 행, 면을 담당할 N, M, H 선언
static int N, M, H;
// 방문배열과 토마토 배열을 3차원으로 선언
static boolean[][][] visited;
static int[][][] arr;
// 토마토 위치를 미리 쌓기 위해 큐를 전역으로 선언
static Queue<int[]> q;
// 토마토 배열 원소들에 깊이값을 저장할 depth 선언
static int depth;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
M = Integer.parseInt(st.nextToken());
N = Integer.parseInt(st.nextToken());
H = Integer.parseInt(st.nextToken());
visited = new boolean[H][N][M];
arr = new int[H][N][M];
q = new LinkedList<>();
// 토마토 배열을 3차원으로 입력받으며 익은 토마토 위치(x,y,z)를 큐에 삽입
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++) {
arr[i][j][k] = Integer.parseInt(st.nextToken());
if(!visited[i][j][k] && arr[i][j][k] == 1) {
visited[i][j][k] = true;
q.offer(new int[]{i, j, k});
}
}
}
}
// 큐에 토마토 위치를 쌓아놓은 후 BFS 호출
BFS();
// 만약 토마토 창고에 익지 않은 토마토가 1개 이상 있다면 -1을 출력
for(int[][] a1 : arr) {
for(int[] a2 : a1) {
for(int num : a2) {
if(num == 0) {
depth = -1;
}
}
}
}
bw.write(depth+"\n");
bw.close();
br.close();
}
/**
* 면 i, 열 j, 행 k 3방향으로 너비우선 탐색을 진행.
* 방문자지 않고 익지 않은 토마토가 있는 3차원 위치라면 해당 원소에 깊이값을 갱신한다.
* 이후 해당 토마토 위치값을 큐에 삽입한다.
*/
static void BFS() {
while(!q.isEmpty()) {
int[] now = q.poll();
for(int dir=0; dir<6; dir++) {
int i = now[0] + dx[dir];
int j = now[1] + dy[dir];
int k = now[2] + dz[dir];
if(isRange(i, j, k)) {
if(!visited[i][j][k] && arr[i][j][k] == 0) {
visited[i][j][k] = true;
arr[i][j][k] = arr[now[0]][now[1]][now[2]]+1;
depth = arr[now[0]][now[1]][now[2]];
q.offer(new int[]{i, j, k});
}
}
}
}
}
static boolean isRange(int x, int y, int z) {
if(0<=x && 0<=y && 0<=z && x<H && y<N && z<M) {
return true;
}
return false;
}
}
출처
- 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.