섹션 8 DFS, BFS - 10. 미로탐색(DFS)

문제 설명

7×7 격자판 미로에서 출발점 (1,1)에서 도착점 (7,7)까지 이동할 수 있는 모든 경로의 수를 구하는 문제입니다.
격자 내 0은 이동 가능한 통로, 1은 이동 불가능한 벽입니다.
이동은 상하좌우 네 방향으로만 가능합니다.

입력 & 출력

입력

• 7×7 정사각형 격자판이 주어집니다. 각 값은 0 또는 1입니다.
• 시작점은 항상 (1,1), 도착점은 (7,7)입니다.

출력

• 첫 줄에 이동 가능한 경로의 수를 출력합니다.

예시

입력:
0 0 0 0 0 0 0
0 1 1 1 1 1 0
0 0 0 1 0 0 0
1 1 0 1 0 1 1
1 1 0 0 0 0 1
1 1 0 1 1 0 0
1 0 0 0 0 0 0

출력:
8

해결 방법

• DFS(깊이 우선 탐색)을 사용해 출발점부터 도착점까지 경로를 따라가며 가능한 모든 경우의 수를 탐색합니다.
• 이미 방문한 곳은 다시 방문하지 않도록 방문 체크 배열을 대신 격자 자체를 1로 바꾸고, 되돌아갈 때 다시 0으로 되돌립니다 (백트래킹).
• 도착 지점 (7,7)에 도달하면 경우의 수를 증가시킵니다.

코드 구현

package partDfsBfs;

import java.util.*;

public class Problem10 {
    static int[] dx = {-1, 0, 1, 0}; // 상우하좌
    static int[] dy = {0, 1, 0, -1};
    static int[][] board;
    static int answer = 0;

    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 (1 <= nx && nx <= 7 && 1 <= ny && ny <= 7 && board[nx][ny] == 0) {
                    board[nx][ny] = 1;
                    DFS(nx, ny);
                    board[nx][ny] = 0;
                }
            }
        }
    }

    public static void main(String[] args) {
        Problem10 T = new Problem10();
        Scanner kb = new Scanner(System.in);
        board = new int[8][8]; // 1-indexed 사용

        for (int i = 1; i <= 7; i++) {
            for (int j = 1; j <= 7; j++) {
                board[i][j] = kb.nextInt();
            }
        }

        board[1][1] = 1; // 시작점 방문 표시
        T.DFS(1, 1);
        System.out.println(answer);
        kb.close();
    }
}

코드 설명

• dx, dy: 상우하좌 4방향 이동을 위한 배열
• DFS(int x, int y): 현재 위치에서 도착지까지 탐색하는 함수
• board[nx][ny] == 0: 통로이면서 아직 방문하지 않은 경우만 이동
• 탐색이 끝나면 board[nx][ny] = 0으로 되돌려 백트래킹 수행

시간 복잡도

• 완전 탐색 구조로, 최악의 경우 최대 4^L까지 호출되지만, 벽(1)이 많아 실제 탐색은 많이 줄어듬
• 제한된 격자 크기(7×7)이므로 완전 탐색이 가능

---

출처: 인프런 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비

https://www.inflearn.com/course/자바-알고리즘-문제풀이-코테대비/dashboard

자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 강의 | 김태원 - 인프런