미로 최단거리 구하기 (BFS)

(1.1) to (7.7) 최단거리 구하기.

 

특징.

1. 레벨 탐색, DFS와 달리 도달하는 경우의 수는 구할 수 없다.

2. dis 배열을 사용해 누적된 거리 값을 기록한다 또는 level 변수를 기록하여 종료되는 시점의 값을 선택한다.

 

실수 체크 포인트

dis[nx][ny]= dis[p.x][p.y] + 1;

-위 식의 이전 dis 값의 인덱스에 BFS의 parameter인 px,py를 잘못 사용함.

level++

-레벨 증가식 위치를 잘못 사용.

 

 

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class Main {

	static int m, n, answer;
	static int LEN =7;
	static int [][]map;
	static int [][]dis; //accumulate distance
	static int[] dx = {0, 0, 1, -1};
	static int[] dy = {1, -1 ,0 ,0 };
	public static void main(String args[]) throws Exception {
		Main M = new Main();
		Scanner in = new Scanner(System.in);
		map = new int[LEN+2][LEN+2];
		dis = new int[LEN+2][LEN+2];
		for ( int i =1 ; i <= LEN ; i++ )
			for( int j =1 ; j <= LEN ; j++)
				map[i][j] = in.nextInt();

		
		M.BFS(1,1);
		/*
		for ( int i =1 ; i <= LEN ; i++ ) {
			for( int j =1 ; j <= LEN ; j++) {
				System.out.print( dis[i][j] + " ");
			}
			System.out.println();
		}
		*/
		
		System.out.println(dis[LEN][LEN]!=0 ? dis[LEN][LEN] : -1);
	}

	private void BFS(int px, int py) {
		Queue<Position> Q = new LinkedList<>();
		Position p = new Position(px, py);
		int level = 0;
		map[px][py]=1;
		dis[px][py]=0;
		Q.offer(p);
		
		
		while( !Q.isEmpty() ) {
			int len = Q.size();
			
			/*i == tree's depth*/
			for (int i = 0 ; i<len ; ++i) {
				p = Q.poll();
				//System.out.println(px +"," +py);
				if( p.x == LEN && p.y == LEN) return;
				
				for ( int j = 0 ; j < 4 ; ++j) {
					int nx = p.x + dx[j];
					int ny = p.y + dy[j];
					if( nx >=1 && nx<=LEN && ny >= 1&& ny <= LEN && map[nx][ny]==0) {
						map[nx][ny]=1;
						//System.out.println(nx +"," +ny);
						dis[nx][ny]= dis[p.x][p.y] + 1;
						Q.offer(new Position(nx, ny));
						
					}					
				}				
				
			}
			level++;
			//System.out.println("level : "+ level);
			
		}
		answer = level;
		
	}

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