[문제풀이] 08-10. 미로 탐색(DFS)

인프런, 자바(Java) 알고리즘 문제풀이

DFS, BFS 활용 - 0810. 미로 탐색(DFS)

🗒️ 문제

🎈 나의 풀이

	private static final int SIZE = 7;
    private static int[][] maze = new int[SIZE][SIZE];
    private static int DFS(int x, int y) {
        if(x == SIZE-1 && y == SIZE-1) return 1;
        int moveUp=0, moveDown=0, moveRight=0, moveLeft=0;

        if(x+1 < SIZE && maze[x+1][y] == 0) {
            maze[x+1][y] = 1;
            moveDown = DFS(x+1, y);
            maze[x+1][y] = 0;
        }
        if(y-1 >=0 && maze[x][y-1] == 0) {
            maze[x][y-1] = 1;
            moveRight = DFS(x, y-1);
            maze[x][y-1] = 0;
        }
        if(x-1 >= 0 && maze[x-1][y] == 0) {
            maze[x-1][y] = 1;
            moveUp = DFS(x-1, y);
            maze[x-1][y] = 0;
        }
        if(y+1 < SIZE && maze[x][y+1] == 0) {
            maze[x][y+1] = 1;
            moveLeft = DFS(x, y+1);
            maze[x][y+1] = 0;
        }

        return moveUp + moveDown + moveRight + moveLeft;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        for(int i=0; i<maze.length; i++) {
            for(int j=0; j<maze.length; j++) {
                maze[i][j] = sc.nextInt();
            }
        }
        maze[0][0] = 1;
        System.out.println(DFS(0, 0));
    }

🖍️ 강의 풀이

  	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);
	}

💬 짚어가기

해당 문제는 DFS를 이용하여 풀 수 있다. 나의 풀이에서는 4가지 조건문을 작성하여
미로의 우측, 좌측, 위, 아래를 탐방하도록 하였다. 이 때 미로의 크기(배열)을 벗어나는
경우와 이미 방문한 칸을 재방문하는 경우를 방지하기 위해 추가적인 조건문을 달았다.

그 다음 DFS를 수행하며 도착 지점에 도달하는 경우 카운트하여 문제를 해결하였다.
나의 코드에서 반복적인 패턴을 없애고 싶었는데 역시 강의의 코드에서 잘 짜져있다.

강의에서는 크기가 4인 dx와 dy 배열을 만들었는데, 한 축이 움직일 때 나머지 축의
요소에 0을 보관하여 반복문을 수행하여 상하좌우를 탐방 할 수 있도록 구현하였다.