일단 충격먹어서, 학기 중에 포스팅을 잘 하지 않았는데도, 포스팅을 한다…
풀이
시뮬레이션 문제이다. bfs를 사용하여 토마토가 익는 것을 퍼뜨린다…여기까진 오케이다. 그 다음으로, 문제가 토마토가 3차원인 정육면체에 들어있으므로, 3차원 배열을 선언하여 토마토를 입력받았다. 그리고, 평소 하던대로 탐색을 시작하였는데…
메모리 초과가 나왔다.
그래서 역시, 3차원 배열로 풀면 안되는 문제였나? 하고 2차원 배열로 풀어봤더니 역시 안된다. (생각해보면 3차원이든 2차원이든 들어오는 데이터의 양은 똑같기 때문에, 차이가 없었나보다.)
이 과정에서 방문을 체크하는 visited배열을 사용하여, 중복으로 큐에 삽입되는 경우도 막아보았지만, 왜 안되는진 모르겠는데 안됐다. 다른 풀이들 보니까 되던데
즉, 아무리 생각해도, 메모리 초과의 이유를 알 수 없었다.
그러다 나와 그냥 똑같은 풀이를 발견하고, 그 차이점을 파악하였다.
바로, 날짜가 흐르는 것을 이미 생성된 배열에서 관리하느냐, 아니면 토마토 객체에서 관리하느냐에 차이였던 것이다. 이게 그렇게 차이가 크다고?하면서 객체에서 관리하던 날짜들을 없애고, 지도에 바로바로 표기하도록 코드를 수정하였더니, 바로 통과가 되었다…
뭐, 그렇다. 딱히 신경쓸 것이라고는 그냥 메모리 관련된 부분에서 3차원으로 받는 데이터를 어떻게 처리할 것인가?이다. 이 과정에서, 객체가 소유하고 있는 데이터가 하나 늘어났을 뿐이지만, 생각 이상으로 메모리에 영향을 끼친다는 점이 놀라웠다.
아래는 오답 코드와 정답 코드의 비교 차원에서 넣은 것이다.
오답 소스 코드
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
import java.util.*;
import java.io.*;
public class Main {
static int[] dh = {1,-1,0,0,0,0};
static int[] dx = {0,0,1,-1,0,0};
static int[] dy = {0,0,0,0,-1,1};
public static void main(String[] args) throws Exception{
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());
int[][][] map = new int[h][n][m];
Queue<Tomato> q = new LinkedList<>();
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++) {
map[i][j][k] = Integer.parseInt(st.nextToken());
if (map[i][j][k] == 1)
//이렇게 객체에서 day를 관리한다.
q.add(new Tomato(i,j,k, 1));
}
}
}
int result = -1;
while (!q.isEmpty()) {
Tomato now = q.poll();
result = Math.max(result, now.day);
map[now.h][now.r][now.c] = now.day;
for (int i = 0; i < 6; i++) {
int nh = now.h+dh[i];
int nr = now.r+dx[i];
int nc = now.c+dy[i];
if (nh >= 0 && nh < h && nr >= 0 && nc >= 0 && nr < n && nc < m) {
if (map[nh][nr][nc] == 0) {
q.add(new Tomato(nh, nr, nc, now.day+1));
}
}
}
}
for (int i = 0; i < h; i++) {
for (int j = 0; j < n; j++) {
for (int k = 0; k < m; k++) {
if (map[i][j][k] == 0) {
System.out.println(-1);
return;
}
}
}
}
System.out.println(result-1);
}
static class Tomato{
int h;
int r;
int c;
int day;
public Tomato(int h, int r, int c, int day) {
this.h = h;
this.r = r;
this.c = c;
this.day = day;
}
}
}
정답 소스 코드
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
import java.util.*;
import java.io.*;
public class 토마토7569 {
static int[] dh = {1,-1,0,0,0,0};
static int[] dx = {0,0,1,-1,0,0};
static int[] dy = {0,0,0,0,-1,1};
public static void main(String[] args) throws Exception{
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());
int[][][] map = new int[h][n][m];
Queue<Tomato> q = new LinkedList<>();
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++) {
map[i][j][k] = Integer.parseInt(st.nextToken());
if (map[i][j][k] == 1)
q.add(new Tomato(i,j,k));
}
}
}
int result = -1;
while (!q.isEmpty()) {
Tomato now = q.poll();
result = Math.max(result, map[now.h][now.r][now.c]);
for (int i = 0; i < 6; i++) {
int nh = now.h+dh[i];
int nr = now.r+dx[i];
int nc = now.c+dy[i];
if (nh >= 0 && nh < h && nr >= 0 && nc >= 0 && nr < n && nc < m) {
if (map[nh][nr][nc] == 0) {
q.add(new Tomato(nh, nr, nc));
//이미 선언된 배열에서 day를 관리한다.
map[nh][nr][nc] = map[now.h][now.r][now.c] + 1;
}
}
}
}
for (int i = 0; i < h; i++) {
for (int j = 0; j < n; j++) {
for (int k = 0; k < m; k++) {
if (map[i][j][k] == 0) {
System.out.println(-1);
return;
}
}
}
}
System.out.println(result-1);
}
static class Tomato{
int h;
int r;
int c;
public Tomato(int h, int r, int c) {
this.h = h;
this.r = r;
this.c = c;
}
}
}
태클 감사합니다.
조언 환영입니다.