Programming/Algorithm
[BFS] BOJ 7569번, 토마토(JAVA)
SNOWOO
2021. 10. 28. 14:12
728x90
문제풀이
이 문제는 이전에 풀었던 토마토 문제의 업그레이드 버전이다
원래 2차원 배열 탐색으로 주어졌던 저번이랑 달리 3차원 배열을 탐색해야 한다.
따라서 방향 벡터가 4개 -> 6개로 추가되는 점 주의해서 저번이랑 똑같이 코딩하면 된다.
2021.10.26 - [Programming/Algorithm] - [BFS] BOJ 7576번, 토마토 (JAVA)
[BFS] BOJ 7576번, 토마토 (JAVA)
토마토 문제 철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다. 창고에 보관되는 토마
snowoo.tistory.com
위 글을 참고하시길 바랍니다.
소스코드
|
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.util.*;
import java.io.*;
class Main{
static int n,m,h;
static boolean[][][] visited;
static int[][][] box;
static int ans;
static int[] dx = {0,0,0,0,1,-1};
static int[] dy = {0,0,1,-1,0,0};
static int[] dh = {1,-1,0,0,0,0};
static Queue<Pos> q = new LinkedList<>();
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
StringTokenizer st;
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];
box = 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++)
{
box[i][j][k] = Integer.parseInt(st.nextToken());
if(box[i][j][k]==1)
{
q.add(new Pos(i,j,k));
visited[i][j][k] = true;
}
}
}
}
bfs();
boolean disable = false;
boolean all_one = true;
for(int i=0;i<h;i++)
{
for(int j=0;j<n;j++)
{
for(int k=0;k<m;k++)
{
if(box[i][j][k] == 0)
disable = true;
else if(box[i][j][k] > 1)
{
all_one = false;
}
}
}
}
if(disable)
{
System.out.println(-1);
}
else if(all_one)
{
System.out.println(0);
}
else
{
System.out.println(ans-1);
}
}
static void bfs()
{
while(!q.isEmpty())
{
Pos p = q.poll();
for(int i=0;i<6;i++)
{
int nh = p.h + dh[i];
int ny = p.y + dy[i];
int nx = p.x + dx[i];
if(nh>=0 && ny>=0 && nx>=0 && nh<h && nx<m && ny<n)
{
if(!visited[nh][ny][nx] && box[nh][ny][nx] == 0)
{
box[nh][ny][nx] = box[p.h][p.y][p.x] + 1;
ans = Math.max(ans, box[nh][ny][nx]);
visited[nh][ny][nx] = true;
q.add(new Pos(nh,ny,nx));
}
}
}
}
}
}
class Pos{
int h,y,x;
public Pos(int h,int y, int x)
{
this.h = h;
this.y = y;
this.x = x;
}
}
|
cs |
https://www.acmicpc.net/problem/7569
7569번: 토마토
첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100,
www.acmicpc.net
LIST