미로탐색(DFS)

이 문제는 7x7 격자판에서 주어진 출발점에서 도착점까지 갈 수 있는 경로의 개수를 구하는 문제다. 격자판에서 1은 벽을 나타내고, 0은 통로를 나타낸다. 상하좌우로만 이동할 수 있으며, 중복되지 않는 경로를 찾아야 한다.

 

1. 문제 설명

• 출발점: (1, 1) 좌표
• 도착점: (7, 7) 좌표
• 벽은 1로 표시되며, 통로는 0으로 표시됨
• 상하좌우로만 이동 가능
• 경로의 수를 구하는 문제

2. 입력 및 출력

• 입력: 7x7 격자판의 정보가 주어진다. 1은 벽, 0은 통로다.
• 출력: 출발점에서 도착점까지 가능한 경로의 개수를 출력한다.

3. 예제

입력 예제:

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

 

4. 문제 해결 아이디어

이 문제는 깊이 우선 탐색(DFS)을 사용하여 출발점에서 도착점까지의 모든 경로를 탐색한다. DFS를 통해 경로를 탐색하며, 탐색 중에는 지나간 길을 방문 표시(1)로 설정해 두었다가, 다시 원래 상태로 돌려주는 백트래킹 기법을 사용한다.

• 각 칸에서 상, 하, 좌, 우로 이동하며 이동할 수 있는 경로를 탐색
• 경로가 유효하면 계속 이동하고, 도착점에 도착하면 경로를 하나 추가
• 벽이거나 이미 방문한 곳은 다시 탐색하지 않음

5. 코드 설명

package com.example.codingtest;

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

class Main {
    // 상, 우, 하, 좌로 이동할 좌표 변화량
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};
    static int[][] board;  // 미로의 정보를 저장하는 2차원 배열
    static int answer = 0; // 경로의 개수를 저장하는 변수

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader (new InputStreamReader(System.in));
        board = new int[8][8];  // 1-based index를 위해 8x8 배열을 사용
        // 7x7 미로 입력을 받음
        for (int i = 1; i <= 7; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= 7; j++) {
                if (st.hasMoreTokens()) {
                    board[i][j] = Integer.parseInt(st.nextToken());
                }
            }
        }
        board[1][1] = 1;  // 출발점을 방문 처리
        DFS(1, 1);  // DFS 탐색 시작
        System.out.println(answer);  // 가능한 경로의 개수 출력
    }

    public static 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 && board[nx][ny] == 0) {
                    board[nx][ny] = 1;  // 방문 처리
                    DFS(nx, ny);  // 다음 위치로 재귀 호출
                    board[nx][ny] = 0;  // 백트래킹 (다시 방문하지 않은 상태로 돌림)
                }
            }
        }
    }
}

 

6. 코드 설명

1. DFS 탐색:
   • 현재 위치가 도착점인 (7, 7)에 도달하면 answer 값을 증가시켜 경로 하나를 찾았음을 표시한다.
   • 상, 하, 좌, 우로 이동 가능한 모든 방향을 탐색한다.
   • 이동 가능한 경우, 방문 처리 후 다시 원래 상태로 돌리기 위해 백트래킹을 사용한다.
2. 경로 탐색:
   • nx와 ny는 각각 상, 하, 좌, 우로 이동할 때의 좌표 변화량을 나타낸다.
   • 이동 가능한 좌표인지 확인한 후, DFS로 재귀적으로 탐색을 진행한다.
   • 백트래킹을 통해 탐색이 끝나면 원래 상태로 복구하여 다른 경로를 탐색할 수 있도록 한다.

7. 핵심 개념

• DFS(깊이 우선 탐색): 경로를 끝까지 탐색한 후, 다시 돌아와 다른 경로를 탐색하는 방식.
• 백트래킹: 탐색 중인 경로가 끝나면, 다시 돌아와 다른 경로를 탐색할 수 있도록 방문 표시를 복구하는 기법.

8. 결론

이 문제는 DFS를 사용한 미로 탐색 문제로, 출발점에서 도착점까지의 모든 경로를 탐색하는 문제다. 백트래킹을 이용하여 효율적으로 경로를 찾아내며, 가능한 모든 경로를 출력한다.