문제
https://www.acmicpc.net/problem/7569
문제 풀이
최소 일 수를 구하는 문제여서 bfs일 거라고 생각하고 문제를 풀었다. 코드 적다가 놓친 부분이 있어서 그 부분을 찾느라 시간이 좀 걸렸다.
1) 런타임 에러
3차 배열을 사용했는데 입력 순서를 제대로 생각 안 하고 만들어서 ArrayIndexOutOfBoundsException가 발생했다. (전날에 밤을 샜따.)
2) 틀렸습니다
이제 에러는 발생 안 하는데 로직에 문제가 있었다.
- 이미 모든 토마토가 익은 상태면 boolean값이 set 변수를 true로 설정해서 0이 출력되도록 했다. set이면 bfs 안 타도록 따로 if문 걸어줘야 했는데 set이어도 bfs를 탄 후, 결과랑 같이 묶어서 if문에서 처리해버렸다.
- 토마토를 익히다가 토마토가 모두 1이 되어도 queue에는 값이 들어있어서 day가 +1 되어서 나타나는 로직으로 코드가 구성되어있었다. 마지막 날에는 (queue가 empty인 상황) day가 +1이 되지 않도록 코드를 작성해야한다.
작성한 코드
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.IOException;
import java.util.StringTokenizer;
import java.util.LinkedList;
import java.util.Queue;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int M = Integer.parseInt(st.nextToken());
int N = Integer.parseInt(st.nextToken());
int H = Integer.parseInt(st.nextToken());
int[][][] 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());
}
}
}
boolean set = 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) {
set = false;
}
}
}
}
if(set) {
bw.write("0\n");
} else{
int day = bfs(box, H, N, M);
if (day == -1) {
bw.write("-1\n");
} else {
bw.write(day + "\n");
}
}
bw.flush();
bw.close();
br.close();
}
public static int bfs(int[][][] box, int H, int N, int M) {
boolean[][][] visited = new boolean[H][N][M];
int day = 0;
int[] dh = {-1, 1, 0, 0, 0, 0};
int[] dn = {0, 0, -1, 1, 0, 0};
int[] dm = {0, 0, 0, 0, -1, 1};
Queue<int[]> queue = new LinkedList<>();
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] == 1) {
visited[i][j][k] = true;
queue.add(new int[]{i, j, k});
}
}
}
}
while (!queue.isEmpty()) {
int size = queue.size();
int change = 0;
for (int i = 0; i < size; i++) {
int[] point = queue.poll();
int h = point[0];
int n = point[1];
int m = point[2];
for (int d = 0; d < 6; d++) {
int nh = h + dh[d];
int nn = n + dn[d];
int nm = m + dm[d];
if (nh >= 0 && nh < H && nn >= 0 && nn < N && nm >= 0 && nm < M) {
if (!visited[nh][nn][nm] && box[nh][nn][nm] == 0) {
visited[nh][nn][nm] = true;
box[nh][nn][nm] = 1;
queue.add(new int[]{nh, nn, nm});
change++;
}
}
}
}
if(change != 0) day++;
}
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) {
return -1;
}
}
}
}
return day;
}
}
틀린 걸 고치면서 코드를 다시 보다보니 필요없는 부분도 있고해서 좀 정리해주었따.
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.IOException;
import java.util.StringTokenizer;
import java.util.LinkedList;
import java.util.Queue;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int M = Integer.parseInt(st.nextToken());
int N = Integer.parseInt(st.nextToken());
int H = Integer.parseInt(st.nextToken());
Queue<int[]> queue = new LinkedList<>();
int[][][] box = new int[H][N][M];
boolean set = true;
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] == 0) set = false;
if(box[i][j][k] == 1) queue.add(new int[]{i, j, k});
}
}
}
if(set) {
bw.write("0\n");
} else{
int day = bfs(box, queue, H, N, M);
bw.write(day == -1 ? "-1\n" : day + "\n");
}
bw.flush();
bw.close();
br.close();
}
public static int bfs(int[][][] box, Queue<int[]> queue, int H, int N, int M) {
int day = 0;
int[] dh = {-1, 1, 0, 0, 0, 0};
int[] dn = {0, 0, -1, 1, 0, 0};
int[] dm = {0, 0, 0, 0, -1, 1};
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
int[] point = queue.poll();
int h = point[0];
int n = point[1];
int m = point[2];
for (int d = 0; d < 6; d++) {
int nh = h + dh[d];
int nn = n + dn[d];
int nm = m + dm[d];
if (nh >= 0 && nh < H && nn >= 0 && nn < N && nm >= 0 && nm < M && box[nh][nn][nm] == 0) {
box[nh][nn][nm] = 1;
queue.add(new int[]{nh, nn, nm});
}
}
}
if(!queue.isEmpty()) day++;
}
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) {
return -1;
}
}
}
}
return day;
}
}
'개발 > 코테 TIL' 카테고리의 다른 글
[99클럽 코테 스터디 TIL#14일차] 프로그래머스 카펫 (0) | 2024.11.17 |
---|---|
[99클럽 코테 스터디 TIL#13일차] 백준 27961 고양이는 많을수록 좋다 (0) | 2024.11.10 |
[99클럽 코테 스터디 TIL#11일차] 백준 25195 Yes or yes (0) | 2024.11.08 |
[99클럽 코테 스터디 TIL#10일차] 백준 18352 특정 거리의 도시 찾기 (0) | 2024.11.07 |
[99클럽 코테 스터디 TIL#9일차] 백준 7562 나이트의 이동 (0) | 2024.11.06 |