프로그래머스 BFS - 게임 맵 최단거리

 

참고하여 코드 작성해봅시다.

 https://tmdrl5779.tistory.com/216

[프로그래머스] 게임 맵 최단거리(Java 자바)

 

 

BFS를 공부하고 있다. 

Breadth Frirst Search 

너비 우선 탐색

 

쉽지 않다. ;.

 

추천을 받아 바킹 독님의 BFS 게시물을 정독했다.

https://blog.encrypted.gg/941

[실전 알고리즘] 0x09강 - BFS

 

다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 탐색하는 알고리즘 

 

import java.util.*;

class Solution {
    
    int[] dx = {1,0,-1,0};
    int[] dy = {0,1,0,-1};
    
    public int solution(int[][] maps) {
        int answer = 0;
        
        int[][] visited = new int[maps.length][maps[0].length];
        
        bfs(maps,visited);
        answer = visited[maps.length-1][maps[0].length-1];
        if(answer == 0){
            answer = -1;
        }
        return answer;
    }
    
    public void bfs(int[][] maps, int[][] visited){
        int x = 0;
        int y = 0;
        visited[x][y]=1;
        
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[] {x,y});
        
        while(!queue.isEmpty()){
            int[] current=queue.remove();
            int cX = current[0];
            int cY = current[1];
            
            for(int i=0;i<4;i++){
                int nX = cX+dx[i];
                int nY = cY+dy[i];
                
                if(nX<0 || nX>maps.length-1 || nY<0 || nY>maps[0].length-1){
                    continue;
                }
                if(visited[nX][nY]==0 && maps[nX][nY]==1){
                    visited[nX][nY] = visited[cX][cY]+1;
                    queue.add(new int[] {nX,nY});
                }
            }
        }
        
    }
}

x,y =0

 

큐생성

 

while문

 

큐 제거한거 current

 

current에 dx,dy더해서 

nx,ny 만듬

 

continue

 

visited=0

maps=1

 

nxny = visited cx+cy +1

 

add(nx,ny)