미로탐색 코드 질문있습니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;

class Main {
    static int n = 7;
    static int[][] map;
    static int count = 0;
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, -1, 0, 1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        map = new int[n][n];
        for (int x = 0; x < n; x++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int y = 0; y < n; y++) {
                map[x][y] = Integer.parseInt(st.nextToken());
            }
        }
        dfs(0, 0);

        System.out.println(count);

    }

    public static void dfs(int x, int y) {
        if (x == n - 1 && y == n - 1) {
            count++;
        } else {
            for (int i = 0; i < 4; i++) {
                int d_x = dx[i] + x;
                int d_y = dy[i] + y;
                if (d_x >= 0 && d_x <= n - 1 && d_y >= 0 && d_y <= n - 1 && map[d_x][d_y] == 0) {
                    map[d_x][d_y] = 1;
                    dfs(d_x, d_y);
                    map[d_x][d_y] = 0;
                }
            }
        }
    }
}

저와 같은 경우는 1부터 시작하지 않고 0부터 시작해서 n전까지를 구해서 진행했는데 인덱스 차이만 있는데 답은 두배씩 나오는지 모르겠습니다.

정답이 8이라고 하면 16으로 나오더라구요. 인덱스를 하나씩 빼줘서 했을 뿐인데 어디가 문제인지 못찾겠네요ㅠ 아니면 놓친부분이 어디에 있는지 모르겠습니다ㅠ

안녕하세요, 인프런 AI 인턴입니다.

tjrwls08088님, 미로 탐색 문제에서 경로를 찾는 과정에서 답이 2배로 나오는 현상에 대해 질문해주셨네요. 제시해주신 코드를 보았을 때, 기본적인 DFS 탐색은 잘 구현되어 있습니다. 하지만, 중복으로 경로를 세는 문제가 발생한 것 같습니다.

코드를 통해서는 직접적인 문제점을 확인하기 어렵지만, 가장 흔하게 발생할 수 있는 문제 중 하나는 시작점이나 도착점을 잘못 설정하여 경로를 중복으로 세는 경우입니다. 시작점을 여러 번 방문하게 되거나, 도착점이 여러 번 카운트되는 상황을 확인해 볼 필요가 있습니다.

또한, n전까지 구한다고 하였는데, 경계 조건 잘못 설정으로 인한 오류가 생길 수 있습니다. 범위 조건 검사 혹은 마킹하는 부분에서 off-by-one 오류가 없는지 다시 한 번 확인하시기 바랍니다.

코드 상에서는 명확한 문제를 찾기 어렵지만, 가능한 문제점을 주의 깊게 살펴보고, 디버깅을 하면서 각 단계별 변수의 값과 경로의 상태를 추적해 보세요. 이는 중복 카운팅을 발견하는 데 도움이 될 수 있습니다.

본 내용과 관련하여 추가적인 정보를 얻고 싶으시다면 Spring Boot Reference Documentation을 참고해보시는 것도 좋습니다. 프로그래밍하며 자주 마주치는 문제들에 관한 해답을 찾을 수 있어요.

질문하신 내용과 정확히 일치하지 않더라도 디버깅을 하는 과정에서 문제를 해결하는 데 도움이 될 수 있습니다. 문제가 계속해서 해결되지 않는다면, 해당하는 사이트의 커뮤니티 혹은 Q&A 섹션에 질문을 올려 도움을 받는 것도 좋은 방법입니다.

인프런 커뮤니티 질문&답변