BFS 미로 찾기 (small)

  Ex)

java

열기 줄바꿈

/*

5 5
#S###
#...#
#.#.#
#....
###G#

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

public class Maze {

	static int MAX_COUNT = 101;
	static char [][] AdjMatrix = new char[MAX_COUNT][MAX_COUNT];
	static int [][] VisitMatrix = new int[MAX_COUNT][MAX_COUNT];
	static int Width; 
	static int Height;
	static int DIRECTION = 4;
	static int [][] DirMatrix = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
	static Queue<Integer> queueRow = new LinkedList<>();
	static Queue<Integer> queueCol = new LinkedList<>();
	static Queue<Integer> queueDis = new LinkedList<>();
	static int Distance = 0;
	static int StartRow;
	static int StartCol;
	static int GoalRow;
	static int GoalCol;
	static int flag = 0;
	
	public static void main(String[] args) {
		
		Scanner scan = new Scanner(System.in);
		Height = scan.nextInt();
		Width = scan.nextInt();
		
		for(int i = 1; i <= Height; ++i) {
			String str = scan.next();
			for(int j = 1; j <= Width; ++j) {
					AdjMatrix[i][j] =  str.charAt(j - 1);
					if('S' == AdjMatrix[i][j]) {
						StartRow = i;
						StartCol = j;
						break;
					}else if('G' == AdjMatrix[i][j]) {
						GoalRow = i;
						GoalCol = j;		
						break;
					}
			}
		}
		// 인접행렬 출력
		for(int i = 1; i <= Height; ++i) {
			for(int j = 1; j <= Width; ++j) {
				System.out.printf(AdjMatrix[i][j] + " ");
			}
				System.out.println();
		}
		BFS(StartRow, StartCol);
		if(0 == flag) {
			System.out.println(-1);
			return;
		}
	}
	
	public static void BFS(int _StartRow, int _StartCol) {
		
		VisitMatrix[_StartRow][_StartCol] = 1;
		queueRow.offer(_StartRow);
		queueCol.offer(_StartCol);
		queueDis.offer(Distance);
		System.out.printf("start: (%d, %d)\n", _StartRow, _StartCol );
		
		while(false == queueRow.isEmpty()) {
			int currRow = queueRow.poll();
			int currCol = queueCol.poll();
			int currDis = queueDis.poll();
 			
			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('G' == AdjMatrix[nextRow][nextCol]) {
					flag = 1;
					System.out.printf("[%d] (%d, %d) -> (%d, %d)\n", nextDis, currRow, currCol, nextRow, nextCol);
					System.out.println(nextDis);
					return;
				 }
				if('#' != AdjMatrix[nextRow][nextCol] &&
					1 <= nextRow && nextRow <= Height &&
					1 <= nextCol && nextCol <= Width	) {
					VisitMatrix[nextRow][nextCol] = 1;
					queueRow.offer(nextRow);
					queueCol.offer(nextCol);
					queueDis.offer(nextDis);
					System.out.printf("[%d] (%d, %d) -> (%d, %d)\n", nextDis, currRow, currCol, nextRow, nextCol);
				}
			}
		}
	}
}

  - S: start 시작 지점

  - G: goal 목표 지점

  - 최단 거리를 구하기 위해서는 BFS를 이용한다.

  - 거리를 카운트 하기 위해 queueDis(tance)를 만든다.

  - flag를 이용해서 답을 찾을 수 있는 경우/ 아닌 경우를 구분한다.

 

 

 

  Note) 입출력 예시

java

열기 줄바꿈

[입력]
5 5
#S###
#...#
#.#.#
#....
###G#

[출력]
6