인프런 커뮤니티 질문&답변
작성한 질문수
선생님이 풀어주신 코드와 로직은 같은데 왜 채점은 타임에러 뜨는지 모르겠습니다.
해결된 질문
작성
·
317
·
수정됨
1
선생님이 풀어주신 코드는 한번 더 확인하는 과정을 거쳐서 board의 수만큼 시간 복잡도가 그만큼 더 늘어나는 것 같아서 익지 않은 토마토의 개수를 세어서 그 수만큼 익으면 days를 반환하는 코드를 짰는데 왜 타임에러가 발생하는지 궁금합니다. 제가 놓치고 있는 부분이 무엇일까요?..
package testSection8;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
class Point{
int x,y;
Point(int x, int y){
this.x = x;
this.y = y;
}
}
public class Main{
static int n,m,days=0,total=0,cnt;
static int[][] board;
static int[] dx = {-1,0,1,0};
static int[] dy = {0,1,0,-1};
static Queue<Point> q = new LinkedList<>();
public int BFS(){
while (!q.isEmpty()){
days++;
int size = q.size();
for(int i=0; i<size; i++){
Point point = q.poll();
for(int j=0; j<4; j++){
int nx = point.x+dx[j];
int ny = point.y+dy[j];
if(nx>=0 && nx<n && ny>=0 && ny<m && board[nx][ny] == 0){
if(++cnt == total) return days;
board[nx][ny] = 1;
q.offer(new Point(nx,ny));
}
}
}
}
return -1;
}
public static void main(String[] args) {
MainT = new Main();
Scanner sc = new Scanner(System.in);
m = sc.nextInt();
n = sc.nextInt();
board = new int[n][m];
for(int i=0; i<n; i++){
for (int j=0; j<m; j++){
board[i][j] = sc.nextInt();
if(board[i][j] == 1) q.offer(new Point(i,j));
else if(board[i][j] == 0) total++;
}
}
System.out.println(T.BFS());
}
}
답변 2
0
김태원
지식공유자
안녕하세요^^
제가 채점해보니 에러 없이 잘 나옵니다.
다만 코드의 뛰어쓰기가 안되어 있어서 그런게 아닌가 싶습니다. MainT로 되어 있었습니다.
Main T = new Main();0
안녕하세요, 찹쌀떡 님, 인프런 AI 인턴이에요.
시간 복잡도가 증가하여 타임에러가 발생하는 원인은 아마도 cnt 변수의 처리 방식 때문일 것으로 보입니다. 현재 cnt 변수는 익은 토마토의 개수를 저장하기 위해 사용되고 있습니다. 그러나 코드를 보면, 한 번의 BFS 탐색에서 모든 익은 토마토를 큐에 넣기 때문에 cnt 값이 증가하는데, 이는 익지 않은 토마토의 개수를 나타내는 total 값과는 무관합니다.
따라서, 익은 토마토를 큐에 넣는 부분에서 익지 않은 토마토의 개수를 세어주는 처리가 필요합니다. 아래와 같이 코드를 수정해보세요:
if(nx>=0 && nx<n && ny>=0 && ny<m && board[nx][ny] == 0){
board[nx][ny] = 1;
q.offer(new Point(nx,ny));
cnt++;
if(cnt == total) return days;
}
이렇게 수정하면, 익은 토마토가 큐에 추가될 때마다 cnt 값이 증가하고, 익지 않은 토마토의 개수를 모두 익혔을 때에는 cnt 값과 total 값이 같아지므로 days를 반환하게 됩니다. 이렇게 수정하시면 타임에러가 발생하는 문제가 해결될 것입니다. 감사합니다!