[프로그래머스] Lv.2 게임 맵 최단거리 JAVA 풀이

문제 Lv.2 게임 맵 최단거리 (bfs)

맵 크기 : n x m 크기 (n과 m은 각각 1 이상 100 이하의 자연수)
현 위치 : 행: 1, 열: 1
도착지 : 행: 5, 열: 5

이동 가능 : 동서남북 (0은 벽, 1은 갈 수 있는 경로)

 

[과정]

 

 최단거리 → bfs

 

 

 1. 여러 루트 중 최단 거리는 Math.min? 큐는 알잘딱깔센!

• 경로가 여러개가 나오는데 그렇다면 Math.min을 써야하는 걸까?
  이경우는 dfs에 해당된다
  
• 큐는 자동으로!
  큐 같은 경우는 가장 가까운 경로부터 탐색한다
  그리고 그 가까운 경로를 큐에 넣고 또 다시 가까운 경로를 탐색한다
  이는 더 짧은 경로부터 먼저 탐색하기 때문에 목적지에 도달한 경로는 무조건 최단 경로!

 

 2. 큐를 다 돌지 않고 최단거리에서 바로 종료한다!

• 종료 if문을 주어서 제일 먼저 도착지에 도달할 시점에 return!

 

 

 [코드]

class Solution {
    static boolean visit[][];
    static int dx[]={0,0,1,-1};
    static int dy[]={1,-1,0,0};
    public int solution(int[][] maps) {
        visit = new boolean[maps.length][maps[0].length];
        return bfs(0,0,maps);
    }
    static int bfs(int x, int y, int[][] arr){
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{x,y,1});
        visit[x][y]=true;
        
        while(!q.isEmpty()){
            int p[] = q.poll();
            if (p[0] == arr.length - 1 && p[1] == arr[0].length - 1) {
                return p[2]; 
            }
            for(int i=0;i<4;i++){
                int nx = p[0] + dx[i];
                int ny = p[1] + dy[i];
                if(0<=nx&&nx<arr.length && 0<=ny&&ny<arr[0].length){
                    if(!visit[nx][ny]&&arr[nx][ny]==1){
                        visit[nx][ny] = true;
                        q.add(new int[]{nx,ny,p[2]+1});
                    }
                }
            }
        }
        return -1;
    }
}

 

 [해설]

 

    static boolean visit[][];
    static int dx[]={0,0,1,-1};  사방탐색
    static int dy[]={1,-1,0,0};  사방탐색
    public int solution(int[][] maps) {
        visit = new boolean[maps.length][maps[0].length];  방문처리
        return bfs(0,0,maps);  bfs 결과 값 자체를 return
    }

    static int bfs(int x, int y, int[][] arr){
        Queue<int[]> q = new LinkedList<>();  큐 선언
        q.add(new int[]{x,y,1});  arr를 인자로 받았지만 큐에는 count 1을 추가
        visit[x][y]=true;  방문처리
        
        while(!q.isEmpty()){
            int p[] = q.poll();  큐에서 뽑기 
            if (p[0] == arr.length - 1 && p[1] == arr[0].length - 1) {  도착지에 오기만하면 즉시 종료
                return p[2]; 거리 카운트 값 출력
            }
            for(int i=0;i<4;i++){  4방향 탐색
                int nx = p[0] + dx[i];
                int ny = p[1] + dy[i];
                if(0<=nx&&nx<arr.length && 0<=ny&&ny<arr[0].length){  지도 범위 안에 있고
                    if(!visit[nx][ny]&&arr[nx][ny]==1){  방문한 적이 없고 갈 수 있는 길이라면
                        visit[nx][ny] = true;  방문처리하고
                        q.add(new int[]{nx,ny,p[2]+1});  큐에 추가하고 경로는 카운트 + 1한다
                    }
                }
            }
        }
        return -1;  큐 빌 때까지 탐색해도 도착지에 도달 못하면 -1 출력
    }

    

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

프로그래머스