BFS 알리바바 미로

  Ex)

<hide/>
package first;
/*
[입력]
5 5
10110
00010
01010
01000 
00011

[출력]
9
*/

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class AlibabaMaze {	
	static int MAX_COUNT = 101;
	static int DIRECTION = 4;
	static int[][] DirMatrix = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
	static int ColumnCnt;
	static int RowCnt;
	static int cnt = 0;
	static int[][] AdjMatrix = new int[MAX_COUNT][MAX_COUNT];
	static int[][] VisitMatrix = new int[MAX_COUNT][MAX_COUNT];
	static Queue<Integer> queueRow = new LinkedList<>();
	static Queue<Integer> queueCol = new LinkedList<>();
	static Queue<Integer> queueDistance = new LinkedList<>();
	static int ShortestDistance = MAX_COUNT * MAX_COUNT;
	static int Distance = 0;
	static int flag = 0;
	
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		RowCnt = scan.nextInt();
		ColumnCnt = scan.nextInt();
		
		int startRow = RowCnt;
		int startCol = 1;

		
		for(int i = 1; i <= RowCnt; ++i) {
			String str = scan.next();
			for(int j = 1; j<= ColumnCnt; ++j) {
				AdjMatrix[i][j] = str.charAt(j-1) - 48;
			}
		}
		BFSmethod(startRow,  startCol, 1, ColumnCnt);
		
		if(flag == 0) {
			System.out.println(-1);
			return;
			
		}
		System.out.println(ShortestDistance + 1);
		
	}
	
	
	public static void BFSmethod(int _startRow, int _startCol, int targetRow, int targetCol) {
		
		VisitMatrix[_startRow][_startCol] = 1;
		queueRow.offer(_startRow);
		queueCol.offer(_startCol);
		queueDistance.offer(Distance);
		
		System.out.println();
		System.out.printf("시작: (%d, %d)\n", _startRow, _startCol);
		
		while(false == queueRow.isEmpty() && false == queueCol.isEmpty()) {
			
			int currRow = queueRow.poll();
			int currCol = queueCol.poll();
			int currDis = queueDistance.poll();
			
			if(currRow == targetRow && currCol == targetCol) {
				flag = 1;
				if(currDis < ShortestDistance) {
					ShortestDistance = currDis;
				}
			}
			for(int i = 0; i < DIRECTION; ++i) {
				
				int nextRow = currRow + DirMatrix[i][0];
				int nextCol = currCol + DirMatrix[i][1];
				int nextDis = currDis + 1;
				
				if(1 == VisitMatrix[nextRow][nextCol] ) continue;
				if(0 == AdjMatrix[nextRow][nextCol] &&
					1 <= nextRow && nextRow <= RowCnt &&
					1 <= nextCol && nextCol <= ColumnCnt ) {
				
					VisitMatrix[nextRow][nextCol] = 1;
					queueRow.offer(nextRow);
					queueCol.offer(nextCol);
					queueDistance.offer(nextDis);
					System.out.printf("[%d]: (%d, %d)->(%d, %d)\n", nextDis, currRow, currCol, nextRow, nextCol) ;
				}
			}
		}	
	}
}

  - int형 flag를 만들어서 최단 경로가 없는 경우에는 -1을 출력한다. 

    -> while문에서 targetRow, targetCol를 만나면 flag에 1을 저장한다.

    -> 만났을 때, currDis가 shortestDistance보다 짧으면 currDis를 shortestDistance에 대입한다. 

  - Queue 객체를 세 가지 만들어서 각각 행, 열, 길이를 넣는다.

  - shortestDistance보다 1을 더해줘야 진짜 최단 길이를 구할 수 있다. 

 

 

  Note) 입출력 예시

<hide/>
[입력]
10 9
000100110
101010001
010010000
001000000
010010011
001100000
001000101
101000010
010011001
001100100

[출력]
-1


[입력]
11 10
0001110000
0010100001
0011100000
0101111010
1000010001
0001000001
1001100111
1101000000
0000100001
0101001001
0001001001

[출력]
22