인프런 커뮤니티 질문&답변
작성한 질문수
완강 후
작성
·
306
1
강사님 강의 너무 잘 듣고있습니다^^ 하루에 4문제 정도 꾸준히 풀고 강의 듣고있습니다. 다름이 아니라 몇일 지나면 강의를 다 볼 것같은데 아직 문제를 딱 보고 뭘 물어보는 문제이고 어떻게 접근해야할지를 정확하게 모르겠어서 해당 강의 문제를 다시 풀어볼려고하는데 .. 새로운 문제를 도전하는게 좋을까요?
답변 2
1
0
안녕하세요 강사님!
저같은 경우에 레벨값을 담고있는 클래스를 따로 만들어
BFS 후 레벨값을 반환하는 식으로 코드를 작성했습니다.
그런데 채점 중에 계속 시간초과가 나와서 질문드립니다.
시간초과가 나는 이유가 뭘까요?
package Inflearn.treegraph;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class 토마토 {
// 토마토 박스
static int[][] box;
// 메모이제이션
static int[][] dp;
static int n;
static int m;
static Queue<Node> queue = new LinkedList<>();
static class Node{
int i;
int j;
int level;
public Node(int i, int j, int level){
this.i = i;
this.j = j;
this.level = level;
}
}
static int bfs(){
int answer = 0;
while (!queue.isEmpty()){
Node node = queue.poll();
int i = node.i;
int j = node.j;
// 토마토가 들어있고, 메모이제이션되지 않았고, i, j가 범위를 넘어서지 않으면
if(validateLocation(i,j) && box[i][j] != -1 && dp[i][j] == 0) {
// 토마토를 익힌다.
if(box[i][j] == 0) box[i][j] = 1;
// 메모이제이션
dp[i][j] = 1;
// 상하좌우 큐에 넣기
queue.add(new Node(i, j-1, node.level+1));
queue.add(new Node(i, j+1, node.level+1));
queue.add(new Node(i-1, j, node.level+1));
queue.add(new Node(i+1, j, node.level+1));
// 정답 갱신
answer = node.level;
}
}
return isThereNotRiped() ? answer : -1;
}
static boolean validateLocation(int i, int j) {
if(i < 0 || i > n-1 || j < 0 || j > m-1) return false;
return true;
}
static boolean isThereNotRiped(){
for(int i = 0 ; i < n ; i ++){
for(int j = 0 ; j < m; j++){
if(box[i][j] == 0) return false;
}
}
return true;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
m = scanner.nextInt();
n = scanner.nextInt();
box = new int[n][m];
dp = new int[n][m];
for(int i = 0; i < n ; i++){
for(int j = 0 ; j < m ; j++){
int x = scanner.nextInt();
if(x == 1){
queue.add(new Node(i, j, 0));
}
box[i][j] = x;
}
}
System.out.println(bfs());
}
}
감사합니다 강사님 열심히 해보겠습니다. 근데 예를들어 문제를 딱 보고 DP로 풀어야되는구나, DFS로 풀어야되는구나 이런 걸 느낄려면 문제를 많이 풀어보면 알아서 저절로 느끼게 되나요?