• 카테고리

    질문 & 답변
  • 세부 분야

    알고리즘 · 자료구조

  • 해결 여부

    미해결

8-11 미로의 최단거리 (BFS)

23.11.29 01:02 작성 조회수 182

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 인턴님의 프로필

인프런 AI 인턴

2023.12.01

안녕하세요, 인프런 AI 인턴입니다.
민표님, 제시해주신 자바 코드를 확인해보니 BFS 알고리즘을 사용해 미로의 최단거리를 구하는 문제를 풀이하신 것 같습니다. 오답이 나올 수 있는 몇 가지 요인을 확인해 볼 수 있습니다:

  1. 조건 검사: 반복문 안에서 미로의 범위를 벗어나는지, 이미 방문한 위치인지의 조건도 필요합니다. 점검된 miro[cl[0] + dx[i]][cl[1] + dy[i]] == 0 조건만으로는 충분하지 않을 수 있습니다. 미로의 벽(1)과 방문한 위치도 (1)로 설정되어 있으니, 방문 여부와 벽을 구분할 수 있는 추가적인 조건이 필요합니다.

  2. 시작점과 도착점 처리: 시작점인 (1,1)을 벽으로 바꾸어두는 miro[1][1] = 1; 조항은 알고리즘 동작에 혼동을 줄 수 있습니다. BFS를 시작하기 전에 시작점을 방문 처리하는 것은 알고리즘의 의도와 일치하지만, 이를 벽으로 변경하는 것은 적절하지 않을 수 있습니다. 마찬가지로 도착점인 (7,7) 또한 올바르게 처리되어야 합니다.

  3. min 변수의 값 설정: min 변수를 사용하여 최단거리를 갱신하는 과정에서 초기값이 0으로 설정되어 있는데, 만약 시작점부터 BFS를 시작하여 도착점에 도달할 수 없는 경우에 대한 예외 처리가 없습니다. 도착점에 도달하지 못했을 경우 어떤 값을 반환할지 고려해야 합니다.

코드의 오류는 이러한 요소들 중 하나 이상 때문일 수 있으니, 조건 검사와 처리 로직을 상세히 살펴보시는 것을 권장드립니다. 만약 수정 후에도 문제가 해결되지 않는다면, 보다 구체적인 오류 메시지나 결과와 함께 질문을 해주시면 추가적인 도움을 드릴 수 있을 것 같습니다.