[JAVA] 알고리즘 문제풀이 - DFS, BFS 기출문제 (미로탐색)

DFS, BFS 기출문제 풀이

미로탐색(DFS)

설명 : 7*7 격자판 미로를 탈출하는 경로의 가지수를 출력하는 프로그램을 작성하세요.

출발점은 격자의 (1, 1) 좌표이고, 탈출 도착점은 (7, 7)좌표이다. 격자판의 1은 벽이고, 0은 통로이다.

격자판의 움직임은 상하좌우로만 움직인다. 미로가 다음과 같다면

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

입력 : 7*7 격자판의 정보가 주어집니다.
출력 : 첫 번째 줄에 경로의 가지수를 출력한다.
풀이 답안

import java.util.*;

public class Main {

    static int[][] map = new int[8][8];
    static int[][] chk = new int[8][8];
    static int result=0;

    public void solution(int x, int y) {

        if(x>7 || y>7 || x<1 || y<1) return;
        if(map[x][y]==0 && chk[x][y]==0){
            chk[x][y]=1;
            if(x==7 && y==7) {
                result++;
            } else {
                solution(x-1, y);
                solution(x+1, y);
                solution(x, y-1);
                solution(x, y+1);
            }
            chk[x][y]=0;
        }
    }

    public static void main(String[] args) {

        Main main = new Main();
        Scanner scan = new Scanner(System.in);
        for(int i=1; i<8; i++){
            for(int j=1; j<8; j++){
                map[i][j] = scan.nextInt();
            }
        }

        main.solution(1, 1);
        System.out.println(result);
    }
}

정리
- 지도의 크기는 고정이기에 이전과 다르게 선언시 바로 크기도 지정으로 생성함
- 이미 방문한 지점은 다시 가지않도록 같은 사이즈의 chk배열도 생성 (그렇지 않으면 같은부분을 무한으로 오가게됨)
- 시작 매개변수는 시작점인 1,1
- 이때 x점과 y점이 지도의 크기를 벗어나면 return되게하고
- 방문한적이 없고, 장애물이 없는(값이 0인) 곳이면 진입
- 체크 여부를 1로 변경해주고 앞뒤좌우 4가지로 재귀변수를 돌게 함
- 도착점 (7,7)에 다다르면 카운트를 증가해줌

IM

DFS, BFS 기출문제 풀이

미로탐색(DFS)