자바(Java) 알고리즘 문제 풀이 - 미로탐색(DFS)

문제 이해

- 미로에서 출발점에서 도착점까지 갈 수 있는 방법의 수를 구하라. 

 

해결 전략

- DFS를 통해 점을 한 칸씩 이동한다.

- 점을 이동하기 전에 board 내부에 있는 점인지, 방문한 적 없는 점인지 체크한다. 

- 한 번 방문한 점은 visited 배열을 통해서 true로 처리한다. 

 

구현

import java.util.*;
class Main {
	static int[] dx={-1, 0, 1, 0};
	static int[] dy={0, 1, 0, -1};
	static int[][] board;
	static boolean[][] visited;
	static int answer=0;

	public void DFS(int x, int y){
	
      if(x == 7 && y == 7){
          answer++;
          return; 
      }else{
           
           for(int i=0; i<4; i++){
              int nx = x+dx[i];
              int ny = y+dy[i];
            
            if(1<=nx && nx<=7 && 1<=ny && ny<=7 && board[nx][ny] == 0 && visited[nx][ny] == false){
                  visited[nx][ny] = true;
                  DFS(nx, ny);
                  visited[nx][ny] = false;
            }
            
          }
          
      }
      
	}

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

 

피드백

- visited 배열을 통해서 방문을 처리할 수 있다.

- 혹은 board배열을 0에서 1로 바꿔서 방문을 처리할 수도 있다.