10. 미로탐색 (DFS)

안녕하세요^^

T.DFS(0, 0)을 호출하기 전에 시작지점인 arr[0][0]을 체크하고 출발해야 합니다.

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

public class Main {

    static int[][] arr;
    static int answer;

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

        for (int i = 0; i < 7; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 7; j++) {
                int tmp = Integer.parseInt(st.nextToken());
                arr[i][j] = tmp;
            }
        }

	arr[0][0] = 1;
        T.DFS(0, 0); // 시작점을 (0, 0)으로 수정
        System.out.println(answer);

    }

    public void DFS(int dx, int dy) {
        if (dx == 6 && dy == 6) { // 종료 조건 수정
            answer++;
        } else {
            int[] dxs = {-1, 0, 1, 0}; // 위, 오른쪽, 아래, 왼쪽 순으로 이동
            int[] dys = {0, 1, 0, -1};

            for (int i = 0; i < 4; i++) {
                int x = dx + dxs[i];
                int y = dy + dys[i];
                if (x >= 0 && x < 7 && y >= 0 && y < 7) {
                    if (arr[x][y] == 0){
                        arr[x][y] = 1; // 방문한 곳을 1로 표시
                        DFS(x, y);
                        arr[x][y] = 0; // 백트래킹: 이전 상태로 돌아감
                    }
                }
            }
        }
    }
}

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

제시하신 코드를 보면 DFS 호출시 arr[x][y] = 1;을 통해 방문한 위치를 표시하고 있으며, 재귀 호출 후에는 arr[x][y] = 0;을 통해 방문 전 상태로 되돌리고 있습니다. 이는 백트래킹을 활용한 잘 구현된 로직입니다.

하지만, 정답값이 두 배로 나오는 문제는 제시된 코드에서 직접적으로 잘못된 부분이 보이지 않습니다. 이 문제가 발생하는 원인으로 생각해볼 수 있는 것은 DFS 함수를 부를 때의 조건이나, 초기 answer값 설정, 혹은 다른 부분에서의 DFS 호출 방식 등에 문제가 있을 수 있습니다.

DFS 함수의 로직 자체는 올바르게 설계되어 재귀적으로 미로 탐색을 수행하고 있습니다. 가능성 있는 오류는 DFS(0, 0); 호출 전에 answer를 초기화하는 과정에서 발생할 수 있습니다. 이 코드에는 answer 초기화하는 부분이 명시되어 있지 않으나, answer가 정상적으로 0으로 초기화되었는지 확인해보세요.

또는, main 함수에서 DFS(0, 0); 호출 이외에 추가적인 호출이 이루어지고 있지는 않은지, main 함수 내부 또는 외부에서 DFS를 중복하여 호출하고 있지는 않은지 등도 검토해볼 필요가 있습니다.

정확한 문제 진단을 위해선 전체적인 실행 흐름을 확인하고, DFS 호출 전후의 상태 변화를 디버그하여 보다 자세히 살펴봐야 할 것 같습니다.