알고리즘) 미로 탐색(DFS 활용)

문제 ✨

풀이 ✨

 이 문제를 트리라고 생각해보면 다음과 같이 접근할 수 있다.

• 시작 노드는 1(값과 달라야 함)이다. (이 때의 레벨을 1로 볼 수 있다.)
• 마지막 노드는 7이다. (이 때의 레벨을 7로 볼 수 있다.)
• 각 노드가 다음 노드로 이동할 수 있는 경우는 자기 자신 노드의 좌표 값(x, y)에서 x는 [0, 1, 0, -1]를 더하고, y는 [-1, 0, 1, 0]를 더한 좌표의 x좌표와 y좌표가 모두 1보다 크거나 같고, 7보다 작거나 같아야 하며, 이전에 왔던 길은 가지 않아야 한다. 또한 그 값이 1인 경우이다. 이 값을 인접 행렬로 정리할 수 있다.
• 레벨을 별도의 변수로 두지 않고, y값이 곧 레벨이라고 여긴다.
• 마지막에 좌표(7, 7)에 도달하는 경우 cnt를 증가시킨다.

import java.util.Scanner;

public class Main {
    static int[][] matrix = new int[8][8];
    static int[] ym = {-1, 0, 1, 0};
    static int[] xm = {0, 1, 0, -1};
    static boolean[][] checked = new boolean[8][8];
    static int cnt = 0;

    void DFS(int y, int x) {
        if (x == 7 && y == 7) cnt++;
        else {
            // 상하좌우 노드 살피기(값이 0인 경우 이동하는 재귀 함수 호출)
            // 왔던 노드가 아닌 이상 값이 0인 경우가 없는 경우에는 더이상 재귀 X
            for (int i = 0; i < 4; i++) {
                int my = y + ym[i];
                int mx = x + xm[i];
                if (my > 0 && my <= 7 && mx > 0 && mx <= 7) {
                    int val = matrix[my][mx];
                    if (val == 0) {
                        if (!checked[my][mx]) {
                            checked[my][mx] = true;
                            DFS(my, mx);
                            checked[my][mx] = false;
                        }
                    }
                }
            }
        }
    }

    public static void main(String[] args) {
        Main main = new Main();
        Scanner sc = new Scanner(System.in);
        for (int i = 1; i <= 7; i++) {
            for (int j = 1; j <= 7; j++) {
                matrix[i][j] = sc.nextInt();
            }
        }

        checked[1][1] = true;
        main.DFS(1, 1);
        System.out.println(cnt);
    }

}