23.11.29 01:02 작성
·
256
0
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
class Main {
static int[][] miro, dis;
static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};
static int min;
static boolean flag;
public static void main(String[] args) {
Main T = new Main();
Scanner sc = new Scanner(System.in);
miro = new int[9][9];
dis = new int[9][9];
min = 0;
flag = false;
for (int i = 0; i < 9; i++) {
if (i == 0 || i == 8) {
for (int j = 0; j < 9; j++) {
miro[i][j] = 1;
}
} else {
miro[i][0]=1;
miro[i][8]=1;
}
}
for (int i = 1; i <= 7; i++) {
for (int j = 1; j <= 7; j++) {
miro[i][j] = sc.nextInt();
}
}
miro[1][1]=1;
dis[1][1]=0;
T.BFS(new int[]{1, 1});
System.out.println(min);
}
void BFS(int[] loca) {
Queue<int[]> Q = new LinkedList<>();
int[] cl = loca;
Q.offer(cl);
while (!Q.isEmpty()) {
if (flag) {
return;
}
cl = Q.poll();
for (int i = 0; i < 4; i++) {
int[] nl = {cl[0] + dx[i], cl[1] + dy[i]};
if (miro[cl[0] + dx[i]][cl[1] + dy[i]] == 0) {
Q.offer(nl);
dis[cl[0] + dx[i]][cl[1] + dy[i]] = dis[cl[0]][cl[1]]+1;
miro[cl[0] + dx[i]][cl[1] + dy[i]] = 1;
if (Arrays.equals(nl,new int[]{7,7})) {
min = dis[cl[0] + dx[i]][cl[1] + dy[i]];
flag = true;
return;
}
}
}
}
}
}
좌표를 클래스로 정의하지 않고 배열로 매개변수를 사용해서 BFS 구현을 하였는데 오답이 나옵니다 ㅜㅜ 출력 12는 나오는데 무엇이 문제일까요??
답변 1
0
안녕하세요, 인프런 AI 인턴입니다.
민표님, 제시해주신 자바 코드를 확인해보니 BFS 알고리즘을 사용해 미로의 최단거리를 구하는 문제를 풀이하신 것 같습니다. 오답이 나올 수 있는 몇 가지 요인을 확인해 볼 수 있습니다:
조건 검사: 반복문 안에서 미로의 범위를 벗어나는지, 이미 방문한 위치인지의 조건도 필요합니다. 점검된 miro[cl[0] + dx[i]][cl[1] + dy[i]] == 0
조건만으로는 충분하지 않을 수 있습니다. 미로의 벽(1
)과 방문한 위치도 (1
)로 설정되어 있으니, 방문 여부와 벽을 구분할 수 있는 추가적인 조건이 필요합니다.
시작점과 도착점 처리: 시작점인 (1,1)을 벽으로 바꾸어두는 miro[1][1] = 1;
조항은 알고리즘 동작에 혼동을 줄 수 있습니다. BFS를 시작하기 전에 시작점을 방문 처리하는 것은 알고리즘의 의도와 일치하지만, 이를 벽으로 변경하는 것은 적절하지 않을 수 있습니다. 마찬가지로 도착점인 (7,7) 또한 올바르게 처리되어야 합니다.
min
변수의 값 설정: min
변수를 사용하여 최단거리를 갱신하는 과정에서 초기값이 0
으로 설정되어 있는데, 만약 시작점부터 BFS를 시작하여 도착점에 도달할 수 없는 경우에 대한 예외 처리가 없습니다. 도착점에 도달하지 못했을 경우 어떤 값을 반환할지 고려해야 합니다.
코드의 오류는 이러한 요소들 중 하나 이상 때문일 수 있으니, 조건 검사와 처리 로직을 상세히 살펴보시는 것을 권장드립니다. 만약 수정 후에도 문제가 해결되지 않는다면, 보다 구체적인 오류 메시지나 결과와 함께 질문을 해주시면 추가적인 도움을 드릴 수 있을 것 같습니다.