[인프런] 08_10 미로탐색(DFS)

📖  문제

---

문제설명

• 7*7 격자판 미로를 탈출하는 경로의 가지수를 출력하는 프로그램을 작성하세요.
• 출발점은 격자의 (1, 1) 좌표이고, 탈출 도착점은 (7, 7)좌표이다. 격자판의 1은 벽이고, 0은 통로이다.
• 격자판의 움직임은 상하좌우로만 움직인다. 미로가 다음과 같다면

미로 예시

• 위의 지도에서 출발점에서 도착점까지 갈 수 있는 방법의 수는 8가지이다.

입력설명

• 7*7 격자판의 정보가 주어집니다.

출력설명

• 첫 번째 줄에 경로의 가지수를 출력한다.

출력 예시

⚠️  주의사항

---

• NullPointer 주의 -> 8 * 8 격자판으로 만들어서 해결

 

✍️  이해

---

/**
 * 예전에 풀었던 산봉우리 문제 재활용 하기
 * 1. 주어진 입력 작성
 * 2. nullpointer 주의하기 위해 배열을 7이 아닌 8로 입력
 * 3. dx dy -> 이동을 위한 배열 변수 생성
 * 4. x, y = 7 -> answer 누적
 * 5. i=0 ~ 4 반복 -> 4방향 보기 때문
 * 6. 이동한 곳이 바깥으로 나가는지 0인지 확인
 *  6-1. 이동하기 전에 배열위치 값을 1 입력 후 DFS 호출 후 다시 0으로 초기화
 * 7. sout(answer)
 */

 

✏️  풀이

---

import java.util.Scanner;

public class Main {

    static int[][] mountain;
    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {-1, 0, 1, 0};
    static int answer;
    public void DFS(int x, int y) {
        if (x == 7 && y == 7) answer++;
        else {
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (nx >= 1 && nx <= 7 && ny >= 1 && ny <= 7 && mountain[nx][ny] == 0) {
                    mountain[x][y] = 1;
                    DFS(nx, ny);
                    mountain[x][y] = 0;
                }
            }
        }
    }
    public static void main(String[] args) {
        Main T = new Main();
        Scanner sc = new Scanner(System.in);

        mountain = new int[8][8];

        for (int i = 1; i <= 7; i++) {
            for (int j = 1; j <= 7; j++) {
                mountain[i][j] = sc.nextInt();
            }
        }
        mountain[1][1] = 1;
        T.DFS(1, 1);
        System.out.println(answer);
    }
}

---