82강 미로탐색

package 섹션8_DFS_BFS심화;

import java.io.*;
import java.util.StringTokenizer;

public class Q10_미로탐색 {
    static int[][] arr; // 미로
    static boolean[][] visited; // 방문 배열
    static int count; // 탈출 경로의 수

    static int[] dx= new int[]{-1,1,0,0};
    static int [] dy= new int[]{0,0,-1,1};


    static void dfs(int x,int y){
        if(x==7 && y==7){ // 도착지점
            count++;
            return;
        }
        for(int i=0;i<4;i++){
            int a = x+dx[i];
            int b = y+dy[i];
            if(a>0 && a<=7 && b>0 && b<=7 && arr[a][b]==0 && !visited[a][b]){ // 조건 검사시 순서도 중요!
                visited[a][b]=true;
                dfs(a,b);
                visited[a][b]=false;
            }
        }

    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        // 미로 생성
        arr = new int[8][8];
        visited = new boolean[8][8];

        for(int i=1;i<=7;i++){
            st = new StringTokenizer(br.readLine());
            for(int j=1;j<=7;j++){
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        visited[1][1]=true;
        dfs(1,1);

        System.out.println(count);

    }
}

 

 

 

✅ 코드 비교 

package 섹션8_DFS_BFS심화;

import java.io.*;
import java.util.StringTokenizer;

public class Q10_미로탐색 {
    static int[][] arr; // 미로
    static int count; // 탈출 경로의 수

    static int[] dx= new int[]{-1,1,0,0};
    static int [] dy= new int[]{0,0,-1,1};


    static void dfs(int x,int y){
        if(x==7 && y==7){ // 도착지점
            count++;
            return;
        }
        for(int i=0;i<4;i++){
            int a = x+dx[i];
            int b = y+dy[i];
            if(a>0 && a<=7 && b>0 && b<=7 && arr[a][b]==0){ // 조건 검사시 순서도 중요!
                arr[a][b]=1;
                dfs(a,b);
                arr[a][b]=0;
            }
        }

    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        // 미로 생성

        arr = new int[8][8];

        for(int i=1;i<=7;i++){
            st = new StringTokenizer(br.readLine());
            for(int j=1;j<=7;j++){
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        arr[1][1]=1; // 출발점 
        dfs(1,1);

        System.out.println(count);

    }
}

 

 

왜 DFS 문제일까? 

출발점- 도착점까지 갈 수 있는 모든 경로를 구하는 문제였다. DFS는 경로를 완전탐색하기 때문에 도착점까지 갈 수 있는 모든 경우의 수를 구할 수 있다. 

그래서 이 문제를  DFS로 풀었다. 

 

수정할 부분

이전에 지나온길을 표시하기 위해 배열을 따로 만들었는데, 굳이 따로 만들지 않고 0을 1로 바꿔주는 방식을 쓰는게 더 나은것 같다. 

조건 검사시 해당 위치의 값이 0 인지 먼저 확인하기 전에, 미로 안에 있는 위치인지 확인을 먼저해야한다. 조건 순서 주의하기