[BFS] 최단 경로 찾기

출발지(빨간색) → 도착지(파란색) 으로 가는 최단경로 구하기

 

 

 

 

 

 

 

import java.util.*;

public class Main {	
	
	// 이동방향
	static int[][] D = {
			{0,1},
			{0,-1},
			{1,0},
			{-1,0}
	};
	
	// MAP
	static int[][] matrix = {
		{0,0,0,0,0},
		{0,1,1,1,1},
		{0,0,0,0,0},
		{1,1,1,1,0},
		{0,0,0,0,0}
	};

	public static void main(String[] args) {				
		
		Scanner sc = new Scanner(System.in);
		// 출발지
		int sRow = sc.nextInt();
		int sCol = sc.nextInt();
		
		// 목적지
		int eRow = sc.nextInt();
		int eCol = sc.nextInt();
		
		System.out.println(bfs(sRow, sCol, eRow, eCol));
	}
	
	public static int bfs(int sRow, int sCol, int eRow, int eCol) {
		int m = matrix.length;	// 가로
		int n = matrix[0].length;	// 세로
		boolean[][] visit = new boolean[m][n];	// 방문체크
		Queue<Node> queue = new LinkedList<Node>();	// 탐색용 큐
		
		// 시작 Node 추가
		queue.add(new Node(sRow, sCol, 0));
		
		while(!queue.isEmpty()) {			
			Node node = queue.poll();	// 큐에서 꺼내서 확인
			int row = node.row;
			int col = node.col;
			int dist = node.dist;
			visit[row][col] = true;					
			
            // 실제 작업 : 현재 Node의 row,col이 eRow, eCol과 같아지면 도착지
			if(row == eRow && col == eCol) {
				return dist;
			}
			
			// 다음 노드 탐색
			for (int i = 0; i < 4; i++) {				
				int nRow = row + D[i][0];	// row이동
				int nCol = col + D[i][1];	// col이동
				if(nRow < 0 || nRow >= m || nCol < 0 || nCol >= n)	// MAP범위를 벗어나면 Skip
					continue;
				if(visit[nRow][nCol])	// 이미 방문했으면 Skip
					continue;
				if(matrix[nRow][nCol] == 1) // 벽이면 Skip
					continue;		
				
				queue.add(new Node(nRow, nCol, dist+1));
			}						
		}
				
		return -1;
    }
	
	// Node 클래스
	static class Node {
		int row;
		int col;
		int dist;
		
		public Node(int row, int col, int dist) {
			this.row = row;
			this.col = col;	
			this.dist = dist;
		}
		
	}
		
}

 

BFS참고 => https://www.youtube.com/watch?v=yQ7o1Y7X_Rg