인프런 영문 브랜드 로고
인프런 영문 브랜드 로고

인프런 커뮤니티 질문&답변

ssun님의 프로필 이미지

작성한 질문수

자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비

12. 토마토(BFS)

마지막 테스트 케이스에서 타임에러 발생하는데 이유를 모르겠어요 (해결완료)

작성

·

21

·

수정됨

0

 

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

public class Main {
    static int n, m, left=0;
    static int[][] boxes;
    static int[][] directions = new int[][]{{-1, 0}, {0, -1}, {1, 0}, {0, 1}};

    static Queue<Integer[]> q;

    public int BFS() {
        /* 정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸 | 모두 익을 때까지의 최소 날짜  nx-1, ny | nx, ny-1 | nx+1, ny | nx, ny+1 */
        if (left==0) return 0;
        int L = 0;
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i=0; i<size; i++) {
                Integer[] point = q.poll();
                for (int j=0; j<4; j++) {
                    int nx = point[0] + directions[j][0];
                    int ny = point[1] + directions[j][1];
                    if (nx>=0 && nx<n && ny>=0 && ny<m && boxes[nx][ny]==0) {
                        left--;
                        boxes[nx][ny] = 1;
                        q.offer(new Integer[]{nx, ny});
                    }
                }
            }
            L++;
        }
        if (left >0) return -1;
        return L-1;
    }

    public static void main(String[] args) {
        Scanner kb = new Scanner(System.in);
        m = kb.nextInt();
        n = kb.nextInt();
        boxes = new int[n][m];
        q = new LinkedList<>();
        for (int i=0; i<n; i++) {
            for (int j=0; j<m; j++) {
                boxes[i][j] = kb.nextInt();
                if (boxes[i][j]==1) q.offer(new Integer[]{i, j});
                if (boxes[i][j]==0) left++;
            }
        }
        Main main = new Main();
        System.out.println(main.BFS());
    }
}

코드는 위와 같이 짰는데 계속 타임 에러가 발생해서 강의를 들었습니다.. 제가 보기엔 강사님이 짜신 거랑 차이를 모르겠는데 제 코드의 어떤 부분이 문제가 됐을까요?

===========================

AI 답변 보고 혹시나 싶어서 강사님이 하신대로 Point class 를 따로 만들어서 진행했더니 해결됐습니다..!!!! 배열로 선언한 것과 차이가 있네요

답변 1

0

인프런 AI 인턴님의 프로필 이미지

안녕하세요, 인프런 AI 인턴입니다.

님께서 작성해주신 코드를 검토해본 결과, 타임 에러가 발생할 수 있는 몇 가지 원인을 확인했습니다.

  1. 큐에서 Integer[] 대신 Point 클래스 사용: 현재 코드에서 Integer[]를 사용해 위치를 저장하고 있지만, Point 클래스와 같은 사용자 정의 클래스를 사용하는 것이 성능 측면에서 더 좋을 수 있습니다. 이는 Java의 오토박싱 문제를 피할 수 있기 때문입니다.

  2. 효율적인 탐색 순서: 큐에서 추출한 후 매번 모든 방향을 검사하므로, 조건 체크를 좀 더 효율적으로 개선할 수 있을 것 같습니다. 예를 들어, 익은 토마토가 바로 인접한 것이 아닌 경우 별도의 규칙을 두어 넘기는 것도 하나의 방법일 수 있습니다.

  3. 반복문 최적화: left 변수를 통해 익지 않은 토마토를 추적하는 부분에서 나머지 조건도 꼼꼼하게 확인해주시면 좋습니다. 이 부분에서 실수로 무한루프에 빠질 가능성도 있으니 주의해야 합니다.

  4. 초기 Queue 크기 확인: 초기 입력에서 q.offer() 하는 부분이 적절한지 확인해 주세요. 초기 boxes 배열에서 0이 잘 제외되고 1인 경우만 큐에 적재되고 있는지 확인해 보세요.

아래의 유사한 게시물도 참고하시면 도움이 되실 것 같습니다:

두 게시물에서 제시된 답변을 참고하시면, 시간 복잡도를 줄이고 코드의 효율성을 개선하는 데 도움이 될 것입니다. 특히, BFS 알고리즘의 효율적인 사용 방법에 대한 팁을 얻을 수 있습니다.

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.

ssun님의 프로필 이미지

작성한 질문수

질문하기