자바(Java) 알고리즘 문제 풀이 - 미로의 최단 거리 통로(BFS)

문제 이해

- 미로에서 출발점에서 도착점까지 갈 수 있는 최단 거리를 구하라. 

 

해결 전략

- BFS를 통해 다음 이동 가능한 점을 큐에 넣습니다.

- dis 배열에 이동 거리를 기록합니다. 

- 방문한 점은 board[x][y] = 1로 바꾸어서 다시 방문하지 않도록 합니다. 

 

구현

class Point{
	public int x, y;
	Point(int x, int y){
		this.x=x;
		this.y=y;
	}
}

public class Main {
	static int[] dx={-1, 0, 1, 0};
	static int[] dy={0, 1, 0, -1};
	static int[][] board, dis;
	public void BFS(int x, int y){
	    
	    Queue<Point> q = new LinkedList<>();
	    Point p = new Point(x,y);
        board[x][y] = 1;
	    q.add(p);
	    
	    while(!q.isEmpty()){
	        Point cur = q.poll();
	        int curX = cur.x;
	        int curY = cur.y;
	        
	        if(curX == 7 && curY == 7){
	            break; 
	        }
	        
	        for(int i=0; i<4; i++){
	            int nx = curX+dx[i];
	            int ny = curY+dy[i];
	            
	            if(1<=nx && nx<=7 && 1<=ny && ny<=7 && board[nx][ny] == 0){
	                board[nx][ny] = 1;
	                dis[nx][ny] = dis[curX][curY] + 1;
	                Point next = new Point(nx,ny);
	                q.add(next);
	            }
	        }
	    }
	    
	
	}

	public static void main(String[] args){
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		board=new int[8][8];
		dis=new int[8][8];
		for(int i=1; i<=7; i++){
			for(int j=1; j<=7; j++){
				board[i][j]=kb.nextInt();
			}
		}
		T.BFS(1, 1);
		if(dis[7][7]==0) System.out.println(-1);
		else System.out.println(dis[7][7]);
	}
}

 

피드백

- 큐는 Queue q = new LinkedList<>(); 와 같이 선언합니다.

- 큐에서 값을 제거할 때는 poll() 메소드를 써야 합니다.

- 방문한 점을 다시 방문하지 않기 위해서 board[x][y] = 1로 변환해줍니다. 

- Point class를 만들어서 사용해야 합니다.