[java, 프로그래머스] 게임 맵 최단거리(Lv.2), BFS 너비 우선 탐색 알고리즘

https://school.programmers.co.kr/learn/courses/30/lessons/1844

프로그래머스

 

너비 우선 탐색(BFS, breadth-first search)
그래프를 완전 탐색하는 방법 중 하나로, 시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘

기능	특징	시간 복잡도(노드 수: V, 에지 수: E)
그래프 완전 탐색	- FIFO 탐색 - Queue 자료구조 이용	O(V + E)

너비 우선 탐색의 핵심 이론
1. BFS를 시작할 노드를 정한 후 사용할 자료구조 초기화하기
2. 큐에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 큐에 삽입하기
3. 큐 자료구조에 값이 없을 때까지 반복하기

 

---

코드

 

import java.util.*;
class Solution {
    //상하좌우
    static int[] dr={0,1,0,-1};
    static int[] dc={1,0,-1,0};
    // 방문 확인
    static boolean[][] visited;
    // 행, 열 길이
	static int row_l, col_l;
	static int[][] maps;
  
    public int solution(int[][] M) {
        maps=M;
       	col_l = maps[0].length; // 행길이
		row_l = maps.length; //열 길이
		visited = new boolean[row_l][col_l];
		BFS(0,0); //(0,0)에서 시작!
		int result=-1;  //방문 안했을때는 -1 출력하기 위하여
		if(visited[row_l-1][col_l-1]==true) { //방문했다면 깊이를 출력!
			result=maps[row_l-1][col_l-1];
		}
		

		return result;
    }
    
   	private static void BFS(int row,int col) {//최초로 도달하는 깊이 찾기 위하여 BFS 사용
		Queue<int []> queue=new LinkedList<>();
		queue.offer(new int[] {row,col}); // 시작 넣어준다.
		while(!queue.isEmpty()){ 
			int now[] =queue.poll();
			visited[row][col]=true; // 꺼낸 현재 노드 방문 true로 바꿔준다.
			for(int i=0;i<4;i++) { //방향을 상하좌우로 4번 탐색해서 가능한 길
				int r=now[0]+dr[i];  
				int c=now[1]+dc[i];
				if(r>=0 &&r<row_l&&c>=0&&c<col_l) { //0보다 크고 진영보다는 작은
					if(maps[r][c] !=0 && !visited[r][c]) { // 갈 수 있는 길이고 방문 안했을 때
						visited[r][c]=true;
						maps[r][c]=maps[now[0]][now[1]]+1; // 어차피 안가는 길이니 맵에 깊이 넣어주기!
						queue.add(new int[] {r,c}); //현재 노드 큐에 넣어주기
					}
				}
			}
		}
	}
}

 

풀이

1. 최소 거리는 BFS에서 최소 깊이를 구하는 것으로 BFS를 사용!

2.  상하좌우를 확인하기 위하여 4가지 방향을 반복해서 탐색

 //상하좌우
    static int[] dr={0,1,0,-1};
    static int[] dc={1,0,-1,0};

 

	for(int i=0;i<4;i++) { //방향을 상하좌우로 4번 탐색해서 가능한 길
				int r=now[0]+dr[i];  
				int c=now[1]+dc[i];

 

3. 깊이는 지나간 map은 사용 안 하므로 map위에 깊이를 표시! 마지막 목표를 방문하였으면 깊이를 출력하고 방문 안 했으면 -1 출력

 

 

 

출처: 백준, Do it! 알고리즘 코딩 테스트 자바 편