https://www.acmicpc.net/problem/7569
7569번: 토마토
첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100,
www.acmicpc.net
|
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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
|
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
public static int[][][] arr;
public static int day = 0;
public static int n;
public static int m;
public static int h;
public static int[] dirX = { -1, 0, 1, 0, 0, 0 };// 상하좌우위아래
public static int[] dirY = { 0, 1, 0, -1, 0, 0 };// 상하좌우위아래
public static int[] dirZ = { 0, 0, 0, 0, -1, 1 };
// 새로 익은 토마토에 대해서만 탐색
static class Tomato {
int x;
int y;
int z;
int day;
public Tomato(int z, int x, int y) { // 초기화
this.x = x;
this.y = y;
this.z = z;
}
}
static Queue<Tomato> queue = new LinkedList<Tomato>();
public static void bfs() {
while (!queue.isEmpty()) {
Tomato tomato = queue.poll();
int x = tomato.x;
int y = tomato.y;
int z = tomato.z;
for (int i1 = 0; i1 < 6; i1++) {
int X = x + dirX[i1];
int Y = y + dirY[i1];
int Z = z + dirZ[i1];
if (X >= 0 && X < n && Y >= 0 && Y < m && Z >= 0 && Z < h) {
if (arr[Z][X][Y] == 0) {
queue.add(new Tomato(Z, X, Y));
arr[Z][X][Y] = arr[z][x][y] + 1;
}
}
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
m = sc.nextInt();
n = sc.nextInt();
h = sc.nextInt();
arr = new int[h][n][m];
for (int i = 0; i < h; i++) {
for (int j = 0; j < n; j++) {
for (int k = 0; k < m; k++) {
arr[i][j][k] = sc.nextInt();
}
}
}
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] == 1) {
queue.add(new Tomato(i, j, k));
}
}
}
}
bfs();
int result = 0;
boolean search = false;
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) {
search = true;
}
result = Math.max(result, arr[i][j][k]);
}
}
}
if (search) {
System.out.println(-1);
} else {
if (result == 1) {
System.out.println(0);
} else {
System.out.println(result - 1);
}
}
}
}
|
cs |
문제를 풀면서 헤맸던 부분
우선 이 문제는 dfs로 풀면안된다. bfs로 풀어야 한다. (처음에 dfs로 풀어서 엄청 헤맸다) 이유는 모든 노드를 탐색하는 것이 아닌 인접한 노드만 탐색하면되기 때문이다 (1과 인접한 상하좌우,위,아래를 1로 해주면되니까!)
두번째,큐에 객체를 넣어주기
3차원배열의 값을 큐에 넣어주는 방법은 그냥 배열을 넣어준 사람도 봤고, 나처럼 객체를 넣어준 사람도 있었다.
왜 객체를 썼냐면 내 눈에는 객체 쓰는게 좀 더 가시적이였다.
Tomato 클래스를 만들어줘서 생성자를 통해 값을 초기화하고 -> 새로들어오는 x,y,z값으로 신속하게 바꿔준 객체를 큐에 넣는게 가시적으로 코드에 보였기 때문이다!
여기서 부턴 실수한 부분을 짚을건데
첫번째,
for (int i1 = 0; i1 < 6; i1++) {
int X = x + dirX[i1];
int Y = y + dirY[i1];
int Z = z + dirZ[i1];
--> 여기서 6번 반복문을 돌려야하는데 4번만 돌렸다..ㅋ
두번쨰,
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] == 1) {
queue.add(new Tomato(i, j, k));
}
}
}
}
bfs();
--> 이렇게 arr에서 1인 값을 전체를 돌면서 찾아낸 다음 큐에 넣고 마지막에 bfs를 돌려야했는데
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] == 1) {
queue.add(new Tomato(i, j, k));
bfs();
}
}
}
}
--> 이렇게 해버렸었다..ㅋ
'알고리즘 > 그래프' 카테고리의 다른 글
| [java 백준]실버 1/2178번 미로찾기 (0) | 2021.10.09 |
|---|---|
| [java 백준] 실버 1/7576번 토마토 (0) | 2021.10.03 |
| [java 백준]실버 2/ 4963번 섬의 개수 (0) | 2021.09.30 |
| [java 백준] 실버 1/2667번 단지번호 붙이기 (0) | 2021.09.29 |
| [java 백준] 실버 4/2331번 반복수열 (0) | 2021.09.26 |
댓글