![[BOJ 17114, Java] Hyper Tomato](/internal-api/media/browser-image?url=%2Fmedia%2Fimage%2Fimported-2cab592b7b5d7bc8-image.jpeg&fit=inside&w=1400&h=1000&q=80)
[BOJ 17114, Java] Hyper Tomato
Java Solution for BOJ Problem 17114, "Hyper Tomato"
Problem Link
[BOJ 17114] (<https://www.acmicpc.net/problem/17114>)
Categories
Implementation, Graph Theory, Graph Traversal, Breadth-First Search (BFS)
Description
Personally, I think this problem really demonstrates just how messy BFS can get.
I’ve known about this problem for a while, and even though the solution itself is well-known and famous, I’ve learned once again that implementing my own solution is a different challenge altogether.
Fast I/O is a given, and if you don’t trim the fat when performing breadth-first search, you’re likely to get a timeout.
I’m not sure if you can solve this using sys.stdin.readline in Python, but fortunately, in Java, I was able to handle it using BufferedReader.
After solving this problem and doing some research, it seems there are smarter ways to solve it, but here I solved it by brutally extending the classic BFS.
-
Input coordinate information into an 11-dimensional array
-
Count unripe tomatoes; record the coordinates of ripe tomatoes
-
Iterate through ripe tomatoes, adding adjacent unripe tomatoes to the list of ripe tomatoes while decrementing the count; repeat this process based on the conditions
-
If the count reaches 0, all tomatoes are ripe, so output the number of days taken
-
If the count does not reach 0, but the number of unripe tomatoes does not change when repeating step (3) on the existing unripe tomatoes, it means they can no longer ripen, so output -1.
When solving this problem, if you handle steps 2 and 3 differently—that is, if you increment the counter every iteration or fail to remove the coordinates of ripe tomatoes that have already been used—you may receive a timeout... I struggled with this for quite a while before finally solving it.
Solution Code
The code is quite long... but I think it’s unavoidable given the use of 11 nested for loops and the need to represent adjacent coordinates.
import java.io.*;
import java.util.*;
public class Main {
public static int tomatoLeft;
/**
* 토마토가 익는 메커니즘을 반영하여 1일 뒤의 배열로 변경하는 함수
*/
public static void ripeTomato(int[][][][][][][][][][][] target, Queue<int[]> tomatoQueue, int[] sizeInfo) {
int[][] movements = new int[][]{
new int[]{1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
new int[]{-1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
new int[]{0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0},
new int[]{0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0},
new int[]{0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0},
new int[]{0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0},
new int[]{0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0},
new int[]{0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0},
new int[]{0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0},
new int[]{0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0},
new int[]{0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0},
new int[]{0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0},
new int[]{0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0},
new int[]{0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0},
new int[]{0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0},
new int[]{0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0},
new int[]{0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0},
new int[]{0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0},
new int[]{0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0},
new int[]{0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0},
new int[]{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1},
new int[]{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1},
};
ArrayList<int[]> ripeList = new ArrayList<>();
for (int[] nowIdx : tomatoQueue) {
for (int[] movement : movements) {
boolean isNotOverIndex = true;
for (int i = 0; i < 11; i++) {
if (0 > nowIdx[i] + movement[i] || nowIdx[i] + movement[i] >= sizeInfo[i]) {
isNotOverIndex = false;
break;
}
}
int nextIdx00 = nowIdx[0] + movement[0];
int nextIdx01 = nowIdx[1] + movement[1];
int nextIdx02 = nowIdx[2] + movement[2];
int nextIdx03 = nowIdx[3] + movement[3];
int nextIdx04 = nowIdx[4] + movement[4];
int nextIdx05 = nowIdx[5] + movement[5];
int nextIdx06 = nowIdx[6] + movement[6];
int nextIdx07 = nowIdx[7] + movement[7];
int nextIdx08 = nowIdx[8] + movement[8];
int nextIdx09 = nowIdx[9] + movement[9];
int nextIdx10 = nowIdx[10] + movement[10];
if (
isNotOverIndex
&& target[nextIdx00][nextIdx01][nextIdx02]
[nextIdx03][nextIdx04][nextIdx05][nextIdx06]
[nextIdx07][nextIdx08][nextIdx09][nextIdx10]
== 0
) {
ripeList.add(
new int[]{
nextIdx00, nextIdx01, nextIdx02,
nextIdx03, nextIdx04, nextIdx05, nextIdx06,
nextIdx07, nextIdx08, nextIdx09, nextIdx10
}
);
}
}
}
tomatoQueue.clear();
for (int[] ripeCoord : ripeList) {
if (
target[ripeCoord[0]][ripeCoord[1]][ripeCoord[2]]
[ripeCoord[3]][ripeCoord[4]][ripeCoord[5]][ripeCoord[6]]
[ripeCoord[7]][ripeCoord[8]][ripeCoord[9]][ripeCoord[10]] == 0
) {
target[ripeCoord[0]][ripeCoord[1]][ripeCoord[2]]
[ripeCoord[3]][ripeCoord[4]][ripeCoord[5]][ripeCoord[6]]
[ripeCoord[7]][ripeCoord[8]][ripeCoord[9]][ripeCoord[10]] = 1;
tomatoLeft -= 1;
tomatoQueue.add(ripeCoord);
}
}
}
public static void main(String[] args) throws IOException {
BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter output = new BufferedWriter(new OutputStreamWriter(System.out));
// 배열 사이즈 입력
int[] storageSize = new int[11];
StringTokenizer sizeInput = new StringTokenizer(input.readLine(), "[ ]");
for (int i = 0; i < 11; i++) {
storageSize[i] = Integer.parseInt(sizeInput.nextToken());
}
// 창고 정보 입력
int[][][][][][][][][][][] tomatoStorage = new int[storageSize[0]][storageSize[1]][storageSize[2]]
[storageSize[3]][storageSize[4]][storageSize[5]][storageSize[6]]
[storageSize[7]][storageSize[8]][storageSize[9]][storageSize[10]];
Queue<int[]> ripeTomatoQueue = new LinkedList<>();
for (int idx10 = 0; idx10 < storageSize[10]; idx10++) {
for (int idx09 = 0; idx09 < storageSize[9]; idx09++) {
for (int idx08 = 0; idx08 < storageSize[8]; idx08++) {
for (int idx07 = 0; idx07 < storageSize[7]; idx07++) {
for (int idx06 = 0; idx06 < storageSize[6]; idx06++) {
for (int idx05 = 0; idx05 < storageSize[5]; idx05++) {
for (int idx04 = 0; idx04 < storageSize[4]; idx04++) {
for (int idx03 = 0; idx03 < storageSize[3]; idx03++) {
for (int idx02 = 0; idx02 < storageSize[2]; idx02++) {
for (int idx01 = 0; idx01 < storageSize[1]; idx01++) {
StringTokenizer storageInfo = new StringTokenizer(input.readLine(), "[ ]");
for (int idx00Counter = 0; idx00Counter < storageSize[0]; idx00Counter++) {
int nowInput = Integer.parseInt(storageInfo.nextToken());
if (nowInput == 1) {
ripeTomatoQueue.add(
new int[]{
idx00Counter, idx01, idx02,
idx03, idx04, idx05, idx06,
idx07, idx08, idx09, idx10
}
);
} else if (nowInput == 0) {
tomatoLeft += 1;
}
tomatoStorage[idx00Counter][idx01][idx02]
[idx03][idx04][idx05][idx06]
[idx07][idx08][idx09][idx10]
= nowInput;
}
}
}
}
}
}
}
}
}
}
}
// 지난 날짜 카운팅 변수 및 모두 익지 못하는 상황을 체크하기 위한 Flag 선언
int dayCounter = 0;
boolean cantComplete = false;
// 모두 익지 않았다면 반복
while (tomatoLeft > 0) {
// 함수를 호출하여 기존 배열 깊은 복사 후 1일 뒤의 배열 확인
int lastTomato = tomatoLeft;
ripeTomato(tomatoStorage, ripeTomatoQueue, storageSize);
// 날짜 1 카운트
dayCounter += 1;
// 아직 다 익지 않았지만 기존이랑 차이가 없다면 전부 익을 수 없는 상황이므로 Flag 변경 후 break
if (tomatoLeft != 0 && tomatoLeft == lastTomato) {
cantComplete = true;
break;
}
}
// 문제 조건에 따라서 출력
if (cantComplete) {
output.write("-1");
} else {
output.write(Integer.toString(dayCounter));
}
output.flush();
output.close();
}
}
댓글 작성
게시글에 대한 의견을 남겨 주세요.