[99클럽 코테 스터디 TIL#12일차] 백준 7569 토마토

문제

https://www.acmicpc.net/problem/7569

 

 

문제 풀이

최소 일 수를 구하는 문제여서 bfs일 거라고 생각하고 문제를 풀었다. 코드 적다가 놓친 부분이 있어서 그 부분을 찾느라 시간이 좀 걸렸다.

 

 

1) 런타임 에러

3차 배열을 사용했는데 입력 순서를 제대로 생각 안 하고 만들어서 ArrayIndexOutOfBoundsException가 발생했다. (전날에 밤을 샜따.)

 

 

2) 틀렸습니다

이제 에러는 발생 안 하는데 로직에 문제가 있었다.

1. 이미 모든 토마토가 익은 상태면 boolean값이 set 변수를 true로 설정해서 0이 출력되도록 했다. set이면 bfs 안 타도록 따로 if문 걸어줘야 했는데 set이어도 bfs를 탄 후, 결과랑 같이 묶어서 if문에서 처리해버렸다.
2. 토마토를 익히다가 토마토가 모두 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;
    }
}