[인프런/DFS/10.미로탐색]

<<풀이>>

 

이 문제는 ch와 DFS 그리고 dx, dy를 잘 적용하면 쉽게 풀 수 있는 문제이다. 

 

우선은 여기서 1,1 점이 시작이라고 했으니깐, 배열 특성상 0,0 부터 생기는 것을 감안해서 가독성을 위해 8,8 로 크기를 맞춰줬다.

 

이렇게 하면 0행 0열 전부 이용은 안하고 1,1부터 시작하게 할 수 있다.

 

그러고 난 뒤에 적절하게 DFS를 만들어주고  7x7 행렬에서 벗어나는 경우는 return 하도록 했다.

 

마지막으로 ch를 둠으로써 이미 지나간 자리는 다시 한 번 돌아가지 못하게 하기위해 ch를 도입했다. 그 지점을 지날 때 ch = 1을 두고 안 지나가면 ch = 0으로 만들어주었다.

 

그 결과 이상없이 문제를 풀 수 있었다 !!

 

전형적인 DFS 문제로서 이제 이런 문제는 손쉽게 풀 수 있다 ㅎㅎ 

import java.util.Scanner;

class Main {
    public static int[] dx = {0, 0, -1, 1};
    public static int[] dy = {-1, 1, 0, 0};
    public static int count = 0;
    public static int[][] ch = new int[8][8];

    private void DFS(int[][] arr, int row, int column) {
        if (row == 7 && column == 7) {
            count++;
            return;
        }

        if (row < 1 || row > 7 || column < 1 || column > 7) {
            return;
        } else if(ch[row][column] != 1 && arr[row][column] == 0){
            ch[row][column] = 1;
            DFS(arr, row + dx[0], column + dy[0]);
            DFS(arr, row + dx[1], column + dy[1]);
            DFS(arr, row + dx[2], column + dy[2]);
            DFS(arr, row + dx[3], column + dy[3]);
            ch[row][column] = 0;
        }
    }



    public static void main(String[] args) throws Exception{
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        int[][] arr = new int[8][8];
        for (int i = 1; i <= 7; i++) {
            for (int j = 1; j <= 7; j++) {
                arr[i][j] = in.nextInt();
            }
        }

        T.DFS(arr, 1, 1);

        System.out.println(count);


    }
}

 

-강사님 풀이-

 

이번에는 강사님과 나의 풀이가 크게 틀리지 않다. 다만, 반복문을 활용해서 조금 더 코드를 깔끔하게 만들었다는 점이다.

for문을 통해 DFS의 수 차이가 나는 것을 볼 수 있다.

그리고 board 역시 static으로 빼줬는데 이렇게도 할 수 있음을 한 번 인지하고 간다 !!

 

외에는 동일하다 ㅎㅎ

 

강사님께 많이 배워서 그런지 풀이 많이 닮아있다 !!

 

오늘도 많이 배워간답

import java.util.*;
class Main {
    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(nx>=1 && nx<=7 && ny>=1 && ny<=7 && board[nx][ny]==0){
                    board[nx][ny]=1;
                    DFS(nx, ny);
                    board[nx][ny]=0;
                }
            }
        }
    }

    public static void main(String[] args){
        Main T = new Main();
        Scanner kb = new Scanner(System.in);
        board=new int[8][8];
        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.print(answer);
    }
}