inflearn logo
강의

강의

N
챌린지

챌린지

멘토링

멘토링

N
클립

클립

로드맵

로드맵

지식공유

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

12. 토마토(BFS)

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

94

ssun

작성한 질문수 1

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 를 따로 만들어서 진행했더니 해결됐습니다..!!!! 배열로 선언한 것과 차이가 있네요

java 코딩-테스트

답변 1

0

인프런 AI 인턴

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

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

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

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

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

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

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

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

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

안녕하세요. 바뀐 채점사이트 관련해서 문의드립니다.

0

33

1

갑자기 채점 사이트가 바뀌었어요

0

34

1

문제 리스트 페이지

0

29

1

채점 사이트 관련 질문드립니다

0

24

1

봉우리 문제 질문입니다

0

84

2

씨름 선수 문제에서 각 선수의 몸무게나 키가 같을 수도 있다면?

0

65

0

이 코드랑 영상 코드중에 뭐가 더 좋은 코드인가요?

0

72

0

가중치 방향 그래프에서 가중치가 0인 간선을 표현하는 방법

0

67

1

좌표 정렬 문제 이 코드가 왜 틀린지 모르겠습니다 ㅠㅠ

0

85

2

6-7 강의에서

0

48

1

6-6. 장난꾸러기 질문 있습니다.

0

46

1

강의 수강후 코딩테스트

0

111

1

answer 변수 사용 여부

0

46

1

2중 for문

1

85

2

2-11. 임시반장정하기 (Runtime Error)

0

63

1

혹시 LinkedList 같은 자료 구조들은 따로 배우지 않나요?

0

70

1

이런 풀이는 어떨까요

0

44

1

자바 스트림 방식의 효율성 질문 드립니다.

0

57

1

알고리즘 자료 구조들..

0

63

1

StringBuilder vs BufferdWriter

0

48

1

원더랜드(프림)

0

50

1

이런 코드는 어떤가요?

0

61

1

bfs 풀이

0

57

1

병합정렬

0

57

1