완강 후

안녕하세요^^

이 강의를 우선 복습하시고, 이 강의에 있는 문제가 아무 도움없이 잘 풀리시면 그때 백준이나 프로그래머스 사이트에 가서 연습하시면 좋을 것 같습니다.

안녕하세요 강사님!

저같은 경우에 레벨값을 담고있는 클래스를 따로 만들어

BFS 후 레벨값을 반환하는 식으로 코드를 작성했습니다.

그런데 채점 중에 계속 시간초과가 나와서 질문드립니다.

시간초과가 나는 이유가 뭘까요?

package Inflearn.treegraph;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class 토마토 {

    // 토마토 박스
    static int[][] box;
    // 메모이제이션
    static int[][] dp;
    static int n;
    static int m;
    static Queue<Node> queue = new LinkedList<>();

    static class Node{
        int i;
        int j;
        int level;
        public Node(int i, int j, int level){
            this.i = i;
            this.j = j;
            this.level = level;
        }
    }

    static int bfs(){
        int answer = 0;
        
        while (!queue.isEmpty()){
            Node node = queue.poll();
            int i = node.i;
            int j = node.j;

            // 토마토가 들어있고, 메모이제이션되지 않았고, i, j가 범위를 넘어서지 않으면
            if(validateLocation(i,j) && box[i][j] != -1 && dp[i][j] == 0) {
                // 토마토를 익힌다.
                if(box[i][j] == 0) box[i][j] = 1;
                // 메모이제이션
                dp[i][j] = 1;
                // 상하좌우 큐에 넣기
                queue.add(new Node(i, j-1, node.level+1));
                queue.add(new Node(i, j+1, node.level+1));
                queue.add(new Node(i-1, j, node.level+1));
                queue.add(new Node(i+1, j, node.level+1));
                // 정답 갱신
                answer = node.level;
            }
        }

        return isThereNotRiped() ? answer : -1;
    }

    static boolean validateLocation(int i, int j) {
        if(i < 0 || i > n-1 || j < 0 || j > m-1) return false;
        return true;
    }

    static boolean isThereNotRiped(){
        for(int i = 0 ; i < n ; i ++){
            for(int j = 0 ; j < m; j++){
                if(box[i][j] == 0) return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        m = scanner.nextInt();
        n = scanner.nextInt();
        box = new int[n][m];
        dp = new int[n][m];

        for(int i = 0; i < n ; i++){
            for(int j = 0 ; j < m ; j++){
                int x = scanner.nextInt();
                if(x == 1){
                    queue.add(new Node(i, j, 0));
                }
                box[i][j] = x;
            }
        }

        System.out.println(bfs());
    }
}