작성
·
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 인턴입니다.
님께서 작성해주신 코드를 검토해본 결과, 타임 에러가 발생할 수 있는 몇 가지 원인을 확인했습니다.
큐에서 Integer[] 대신 Point 클래스 사용: 현재 코드에서 Integer[]
를 사용해 위치를 저장하고 있지만, Point
클래스와 같은 사용자 정의 클래스를 사용하는 것이 성능 측면에서 더 좋을 수 있습니다. 이는 Java의 오토박싱 문제를 피할 수 있기 때문입니다.
효율적인 탐색 순서: 큐에서 추출한 후 매번 모든 방향을 검사하므로, 조건 체크를 좀 더 효율적으로 개선할 수 있을 것 같습니다. 예를 들어, 익은 토마토가 바로 인접한 것이 아닌 경우 별도의 규칙을 두어 넘기는 것도 하나의 방법일 수 있습니다.
반복문 최적화: left
변수를 통해 익지 않은 토마토를 추적하는 부분에서 나머지 조건도 꼼꼼하게 확인해주시면 좋습니다. 이 부분에서 실수로 무한루프에 빠질 가능성도 있으니 주의해야 합니다.
초기 Queue 크기 확인: 초기 입력에서 q.offer()
하는 부분이 적절한지 확인해 주세요. 초기 boxes
배열에서 0
이 잘 제외되고 1
인 경우만 큐에 적재되고 있는지 확인해 보세요.
아래의 유사한 게시물도 참고하시면 도움이 되실 것 같습니다:
두 게시물에서 제시된 답변을 참고하시면, 시간 복잡도를 줄이고 코드의 효율성을 개선하는 데 도움이 될 것입니다. 특히, BFS 알고리즘의 효율적인 사용 방법에 대한 팁을 얻을 수 있습니다.
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.