![[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になったらすべて熟したことになるため、かかった日数を出力
-
カウントが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();
}
}
댓글 작성
게시글에 대한 의견을 남겨 주세요.