문제 링크
분류
구현(implementation), 그래프 이론(graphs), 그래프 탐색(graph_traversal), 너비 우선 탐색(bfs)
설명
개인적으로 BFS가 어디까지 더러워질 수 있는지를 잘 보여주는 문제라고 생각한다.
문제의 존재는 진즉에 알고 있었고, 해결법 자체도 이미 유명한만큼 잘 알려져 있어도 내가 해결하는 방식을 구현하는 것이랑은 다른 문제라는 것을 새삼 배워가게 된다.
빠른 입출력은 기본이고, 너비 탐색을 하는 것에 있어서 군더더기를 날려주지 않는다면 시간 초과를 받을 수 있는 문제.
파이썬에서 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();
}
}
24시간은 부족한 게 맞다