선생님이 풀어주신 코드와 로직은 같은데 왜 채점은 타임에러 뜨는지 모르겠습니다.
선생님이 풀어주신 코드는 한번 더 확인하는 과정을 거쳐서 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를 반환하게 됩니다. 이렇게 수정하시면 타임에러가 발생하는 문제가 해결될 것입니다. 감사합니다!
안녕하세요. 바뀐 채점사이트 관련해서 문의드립니다.
0
28
1
갑자기 채점 사이트가 바뀌었어요
0
32
1
문제 리스트 페이지
0
29
1
채점 사이트 관련 질문드립니다
0
23
1
봉우리 문제 질문입니다
0
81
2
씨름 선수 문제에서 각 선수의 몸무게나 키가 같을 수도 있다면?
0
64
0
이 코드랑 영상 코드중에 뭐가 더 좋은 코드인가요?
0
72
0
가중치 방향 그래프에서 가중치가 0인 간선을 표현하는 방법
0
67
1
좌표 정렬 문제 이 코드가 왜 틀린지 모르겠습니다 ㅠㅠ
0
85
2
6-7 강의에서
0
48
1
6-6. 장난꾸러기 질문 있습니다.
0
45
1
강의 수강후 코딩테스트
0
110
1
answer 변수 사용 여부
0
44
1
2중 for문
1
85
2
2-11. 임시반장정하기 (Runtime Error)
0
63
1
혹시 LinkedList 같은 자료 구조들은 따로 배우지 않나요?
0
70
1
이런 풀이는 어떨까요
0
44
1
자바 스트림 방식의 효율성 질문 드립니다.
0
57
1
알고리즘 자료 구조들..
0
62
1
StringBuilder vs BufferdWriter
0
48
1
원더랜드(프림)
0
50
1
이런 코드는 어떤가요?
0
61
1
bfs 풀이
0
57
1
병합정렬
0
56
1





