BFS

백준 7569번 문제를 BFS를 이용하여 Java로 풀어보았다.
이유를 도저히 모르겠는데 코드를 수정하기 전에는 계속해서 3차원 배열 입력이 안됐다. 디버깅을 수십 차례 할 때마다 마지막 한 줄에서 갑자기 끝나버리는데 개빡쳐서 쌍욕을 몇 번 했는지 모르겠다.

BFS로 풀면 로직 자체는 매우 간단한 문제다. 초반에 안돼서 개빡쳤다. 1시간 날렸다. 썅

---

BFS로 익지 않은 토마토 추가해주기

처음에 입력을 받을 때 이미 익은 녀석들을 큐에 추가해주고, 입력을 마친 후에 큐의 원소들을 하나씩 꺼내며 그 주변의 익지 않은 토마토들을 큐에 추가해준다. 익지 않은 토마토들을 큐에 추가해줄 때, 추가로 새롭게 익은 녀석들의 좌표에는 이전의 녀석의 좌푯값에 1씩 추가해주는 작업을 한다. 그렇게 되면 가장 큰 값을 가진 좌표가 곧 며칠이 걸렸는지 알 수 있는 지표가 된다. 딱 하루가 걸렸으면 1에서 1이 추가된 2가 최댓값일테니까 2에서 1을 뺀 1이 걸린 날 수다.

아래 코드가 BFS를 통해 익을 수 있는 녀석들을 다 추가하고 익히는 과정을 작성한 코드다.

while(!alreadyRipe.isEmpty()){
            Pos cur = alreadyRipe.poll();
            for(int dir=0; dir<6; dir++){
                Pos next = new Pos(cur.height+move[dir][0], cur.row+move[dir][1], cur.col+move[dir][2]);
                if(isInRange(next.height,next.row,next.col)){
                    if(map[next.height][next.row][next.col]==0){
                        alreadyRipe.add(next);
                        map[next.height][next.row][next.col] = map[cur.height][cur.row][cur.col] + 1;
                    }
                }
            }
        }

---

전체 토마토 순회하며 안 익은 놈 있나 확인하기

아직 익지 않은 놈이 있으면 문제 조건대로 -1을 출력하고, 만약 최대의 좌푯값이 1이면 이미 다 익은 놈밖에 없던 것이므로 0을 출력한다. 최대 좌푯값이 2이상이면 그 최댓값에서 1을 뺀 값이 곧 걸린 총 날 수이므로 max-1을 출력해주면 된다.
아래가 이 과정을 작성한 코드다 .

int max = 0;
        for(int i=0; i<h; i++){
            for(int j=0; j<n; j++){
                for(int k=0; k<m; k++){
                    if(map[i][j][k]==0) {
                        bfw.write("-1");
                        bfw.close();
                        return;
                    }
                    if(max<map[i][j][k])    max = map[i][j][k];
                }
            }
        }
        if(max==1)  bfw.write("0");
        else{
            bfw.write(String.valueOf(max - 1));
        }

---

아래는 전체 코드다.

import java.util.Queue;
import java.util.StringTokenizer;
import java.util.LinkedList;
import java.io.*;

public class boj7569 {
    static int m, n, h;
    static int[][][] map;
    static boolean[][][] visited;
    static Queue<Pos> alreadyRipe = new LinkedList<>();
    static int[][] move = {{-1, 0, 0}, {1, 0, 0}, {0, -1, 0}, {0, 1, 0}, {0, 0, -1}, {0, 0, 1}}; // 위 아래 앞 뒤 좌 우

    public static void main(String args[]) throws IOException {
        BufferedReader bfr = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bfw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer stk = new StringTokenizer(bfr.readLine());
        m = Integer.parseInt(stk.nextToken());
        n = Integer.parseInt(stk.nextToken());
        h = Integer.parseInt(stk.nextToken());
        map = new int[h][n][m]; visited = new boolean[h][n][m];
        for(int i=0; i<h; i++){
            for(int j=0; j<n; j++){
                stk = new StringTokenizer(bfr.readLine());
                for(int k=0; k<m; k++){
                    map[i][j][k] = Integer.parseInt(stk.nextToken());
                    if(map[i][j][k]==1) alreadyRipe.add(new Pos(i,j,k));
                }
            }
        }

        while(!alreadyRipe.isEmpty()){
            Pos cur = alreadyRipe.poll();
            for(int dir=0; dir<6; dir++){
                Pos next = new Pos(cur.height+move[dir][0], cur.row+move[dir][1], cur.col+move[dir][2]);
                if(isInRange(next.height,next.row,next.col)){
                    if(map[next.height][next.row][next.col]==0){
                        alreadyRipe.add(next);
                        map[next.height][next.row][next.col] = map[cur.height][cur.row][cur.col] + 1;
                    }
                }
            }
        }

        int max = 0;
        for(int i=0; i<h; i++){
            for(int j=0; j<n; j++){
                for(int k=0; k<m; k++){
                    if(map[i][j][k]==0) {
                        bfw.write("-1");
                        bfw.close();
                        return;
                    }
                    if(max<map[i][j][k])    max = map[i][j][k];
                }
            }
        }
        if(max==1)  bfw.write("0");
        else{
            bfw.write(String.valueOf(max - 1));
        }
        bfw.close();
    }

    static Boolean isInRange(int height, int row, int col) {
        if (height < 0 || height >= h || row < 0 || row >= n || col < 0 || col >= m) return false;
        return true;
    }

    static class Pos {
        int height;
        int row;
        int col;

        Pos(int h, int r, int c) {
            this.height = h;
            this.row = r;
            this.col = c;
        }
    }
}

처음에 0을 출력할 때랑 max-1을 출력할 때를 구분해주지 않았더니 틀리게 나왔다. 0을 출력할 때도 어차피 max값이 1이기 때문에 max-1로 퉁 쳤더니 그걸 틀리게 인식하나보다.