백준 7569번 : 토마토 (z축)
이번 문제는 이전에 풀었던 토마토 문제와 같은데, Z축이 추가된 문제이다.
따라서, 문제에 대한 자세한 설명은 토마토 포스트를 보면 알 수 있다.
같은 날에 푼 10026번 적록색약 문제를 포스트할까 이번 문제를 포스트할까 고민했는데, 적록색약 문제의 경우는 크게 어려운 것 없이 일반 탐색과 G를 R로 변경 후 탐색하는 두 가지만 알면 되서 넘어간다.
오히려 3차원 배열에 익숙치 않아 헤맸던 이번 문제가 포스트하기에 적절하다고 생각했다.
앞서 말했듯이 3차원 배열을 활용하여 문제를 푼 것은 이번이 처음인 것 같다.
사실 이전 토마토 문제와 같기 때문에 “3차원 배열을 쓴다.”라는 것만 인지하면 금방 풀 수 있다.
그런데, 3차원 배열에서 x,y,z 를 표현하는 방법과 순서를 몰라서 헤맨 경우이다.
탐색하기 앞서 여타 문제와 같이 그래프를 먼저 그려보았다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static void main(String[] args) throws java.io.IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int m = Integer.parseInt(st.nextToken());
int n = Integer.parseInt(st.nextToken());
int h = Integer.parseInt(st.nextToken());
arr = new int[h][n][m];
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 (arr[i][j][k] == 1) {
q.offer(new int[]{i,j,k});
}
}
}
}
메인 함수 내에 기존과 같이 br과 st로 순서대로 가로, 세로, 높이를 받아 온 다음 그래프로 표현될 arr의 크기를 지정해주었다.
이때, 그래프인 3차원 배열 arr은 순서대로 높이, 세로, 가로로 표현된다.
다음으로 그래프를 구현했는데, if 조건을 빼고 봐야한다.
3중 반복문을 순서대로 높이, 세로, 가로로 실행시켰으며, 높이는 구역을 분리한다고 생각하면 기존 그래프 생성 로직과 동일하다.
이제 그래프도 그려졌으니 탐색 시에 공통적으로 활용할 변수와 방향을 나타내는 배열을 먼저 클래스 멤버 변수로 선언, 초기화했다.
1
2
3
4
5
static int[][][] arr;
static int[] dx = {-1, 0, 1, 0, 0, 0};
static int[] dy = {0, 1, 0, -1, 0, 0};
static int[] dz = {0, 0, 0, 0, -1, 1};
static Queue<int[]> q = new LinkedList<>();
기존 그래프를 나타내던 arr 3차원 배열을 탐색 시에도 활용해야하기 때문에 클래스 멤버 변수로 선언하고, dx, dy, dz는 각각 x축, y축, z축을 나타낸다.
여기서 z축의 방향 배열이 까다로워 구글링 참고했다.
또한 앞선 2차원 배열 토마토 문제를 참고하여 arr 내의 1인 요소를 찾으면 즉시 탐색을 시작해야하므로 멤버 변수로 큐를 생성, 초기화했다.
여기서 m,n,h도 공통으로 사용하기 때문에 넣어줄까 하다가 이 부분은 매개변수로 활용했다.
그래프와 공통 변수를 생성 했으니 탐색할 차례이다.
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
public static int bfs(int m, int n, int h) {
while (!q.isEmpty()) {
int[] cur = q.poll();
for (int i = 0; i < 6; i++) {
int nx = cur[2] + dx[i];
int ny = cur[1] + dy[i];
int nz = cur[0] + dz[i];
if (nx >= 0 && ny >= 0 && nz >= 0 && nx < m && ny < n && nz < h) {
if (arr[nz][ny][nx] == 0) {
q.offer(new int[]{nz, ny, nx});
arr[nz][ny][nx] = arr[cur[0]][cur[1]][cur[2]] + 1;
}
}
}
}
int max = 0;
for (int i = 0; i < h; i++) {
for (int j = 0; j < n; j++) {
for (int k = 0; k < m; k++) {
if (arr[i][j][k] == 0) {
return -1;
}
max = Math.max(max, arr[i][j][k]);
}
}
}
if (max == 1) return 0;
else return max - 1;
}
탐색 알고리즘은 사실 앞서말한 이전 토마토 문제와 동일하다.
bfs 탐색 실행 직전에 arr의 요소가 1인 것을 만나면 해당 위치를 탐색 시작점으로 지정하는 방식인데, 앞선 3중 반복문에서 시작 위치를 받아왔으니 탐색을 돌려 이 결과 값을 리턴하면 된다.
크게 다른 점은 nz, 즉, 다음 z축을 지정해주는 것이다.
또한, 기존 상하좌우 4번이 아닌 상하좌우+위아래 6 방향을 탐색해야한다.
여기서 배열의 값을 순서대로 z,y,x 로 잡았는데, 이게 자꾸 헷갈려서 배열의 범위를 벗어나는 상황이 발생했었다.
그래서 arr 배열의 순서와 맞추어 cur로 저장되는 방향의 순서를 z, y, x로 동일하게 지정했다.
다음 방향을 잡았다면 조건문으로 각 방향이 범위를 벗어나지 않는지 파악해주고, 벗어나지 않는다면 조건을 한번 더 분기하여 해당 위치가 익지 않은 토마토인 0이 있는 위치인지 파악한다.
파악이 되었으면 다시 도달한 위치를 시작점으로 q에 삽입하고 기존 위치 + 1로 지나왔음을 표현하고 일수를 중첩시킨다.
이 로직이 반복되면 도달한 곳 마다 해당 위치까지의 토마토가 모두 익을 때까지 걸리는 총 일수가 기록된다.
마지막으로 arr을 브루트포스식으로 순회하여 0이 하나라도 존재하면 전부 익지 않은 것이기 때문에 -1을, 0이 없는데, 가장 큰 값이 1이라면 0을
이외에는 가장 순회하여 가장 큰 값을 찾아내고, 시작인인 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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static int[][][] arr;
static int[] dx = {-1, 0, 1, 0, 0, 0};
static int[] dy = {0, 1, 0, -1, 0, 0};
static int[] dz = {0, 0, 0, 0, -1, 1};
static Queue<int[]> q = new LinkedList<>();
public static void main(String[] args) throws java.io.IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int m = Integer.parseInt(st.nextToken());
int n = Integer.parseInt(st.nextToken());
int h = Integer.parseInt(st.nextToken());
arr = new int[h][n][m];
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 (arr[i][j][k] == 1) {
q.offer(new int[]{i,j,k});
}
}
}
}
System.out.println(bfs(m, n, h));
}
public static int bfs(int m, int n, int h) {
while (!q.isEmpty()) {
int[] cur = q.poll();
for (int i = 0; i < 6; i++) {
int nx = cur[2] + dx[i];
int ny = cur[1] + dy[i];
int nz = cur[0] + dz[i];
if (nx >= 0 && ny >= 0 && nz >= 0 && nx < m && ny < n && nz < h) {
if (arr[nz][ny][nx] == 0) {
q.offer(new int[]{nz, ny, nx});
arr[nz][ny][nx] = arr[cur[0]][cur[1]][cur[2]] + 1;
}
}
}
}
int max = 0;
for (int i = 0; i < h; i++) {
for (int j = 0; j < n; j++) {
for (int k = 0; k < m; k++) {
if (arr[i][j][k] == 0) {
return -1;
}
max = Math.max(max, arr[i][j][k]);
}
}
}
if (max == 1) return 0;
else return max - 1;
}
}
계속 “이전에 풀었던 토마토 문제”와 같다고 계속 얘기하는데 진짜 똑같다.
Z축 말고는 정말 크게 바뀌는 로직이 없다.
그런데 왜 그럼 가져왔느냐 하면 그냥 3차원 배열을 기억하기 위해서이다.
이번 문제를 풀면서 많이 느낀게, 참고를 하면서 풀 수 있으면 골드 하위 문제
손 대기도 힘들고 다 풀어도 이해가 힘들면 골드 중간 수준 문제 인 것 같다.
발전하고 있다면 그렇다고 할 수는 있겠지만, 코딩 테스트를 보기 위한 준비이기 때문에 나보다 잘하는 사람은 많고 갈 갈이 멀다.