![[BOJ 17114, Java] 超级番茄](/internal-api/media/browser-image?url=%2Fmedia%2Fimage%2Fimported-2cab592b7b5d7bc8-image.jpeg&fit=inside&w=1400&h=1000&q=80)
[BOJ 17114, Java] 超级番茄
BOJ 17114，“超番茄”题的 Java 解法
题目链接
[BOJ 17114] (<https://www.acmicpc.net/problem/17114>)
分类
实现(implementation), 图论(graphs), 图遍历(graph_traversal), 广度优先搜索(bfs)
说明
我个人认为这是一个很好地展示了BFS可以变得多么“臃肿”的题目。
虽然我很早就知道这道题的存在，且解法本身也已广为人知，但这次我再次体会到：即使解法广为人知，将其以自己的方式实现却是另一回事。
快速输入输出是基础，而在进行广度优先搜索时，如果不剔除冗余部分，就可能导致超时。
虽然不确定在Python中能否通过sys.stdin.readline解决，但在Java中幸运的是，仅通过BufferedReader就能处理。
解完这道题后查阅资料发现，似乎另有更巧妙的解法，但这里采用的是对经典BFS进行粗暴扩展的方式来解决。
-
将坐标信息输入到11维数组中
-
未成熟的西红柿进行计数，成熟的西红柿记录坐标
-
遍历成熟的西红柿，将相邻的未成熟西红柿加入成熟西红柿列表的同时减少计数值，根据条件重复该过程
-
若计数值变为0，则表示全部成熟，输出耗时天数
-
若计数未归零，但在对现有未成熟的西红柿重复执行第(3)步操作时数量未发生变化，则说明无法继续催熟，因此输出-1。
在解决此题时，处理第2步和第3步时若采用其他方式——**即每次循环都重新计数，或者不移除已使用过的成熟番茄的坐标，可能会导致超时……**我在此处纠结了很久才解决。
解题代码
代码相当长……但我认为这是因为使用了11层for循环，并且需要表示相邻坐标，所以无可奈何。
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();
}
}
댓글 작성
게시글에 대한 의견을 남겨 주세요.