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

강의 너무나 잘 듣고 있습니다.

해당 강의에서, 정점을 가지고 for문을 돌 때 방문 체크를 해주었는데, 저처럼 DFS 함수 진입시 정점 방문을 해주는 코드는 맞지 않는 코드인가요?? 정답은 나옵니다 6!

import java.util.Scanner;

public class 경로탐색_인접행렬 {
    static int answer = 0, n,m;
    static int[][] graph;
    static boolean[] check;


    static void DFS(int v){
        check[v] = true;
        if (v == n) answer++;

        for (int i = 1; i < graph[v].length; i++){
            if(graph[v][i] == 1 && !check[i]){
                DFS(i);
                check[i] = false;
            }
        }
    }



    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        check = new boolean[n + 1];
        graph = new int[n + 1][n + 1];
        for (int i = 0; i < m; i++){
            int x = sc.nextInt();
            int y = sc.nextInt();
            graph[x][y] =  1;
        }
        DFS(1);
        System.out.println(answer);
    }
}