[JAVA]프로그래머스_게임맵최단거리

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

코딩테스트 연습 - 게임 맵 최단거리

 

문제 유형 :  BFS

 

풀이 방식 

- BFS를 이용

- BFS while 문 안 처음 for문을 큐 사이즈만큼만 돌려준다. (같은 레벨? 뎁스? 만큼만 돌리고 턴 카운트 해주기위해서)

- 근데 큐 폴할때 최종지점인지 확인하면 안되고 넣을때 확인하면 되는걸까...?

 

 

소스코드

import java.util.*;
class Solution {
    public int solution(int[][] maps) {
        int answer = -1;
        int n = maps.length, m = maps[0].length;
        int[] dr = {0,0,1,-1}, dc = {1,-1,0,0};
        Queue<int[]> q = new LinkedList<int[]>();
        boolean[][] visited = new boolean[n][m];
        q.offer(new int[]{0,0});
        visited[0][0] = true;
        boolean flag = false; // 상대 팀 진영을 파괴 유무 확인용
        int count = 0;
loop:   while(!q.isEmpty()){
            count++;
            int qSize = q.size();
            for(int i=0; i<qSize; i++){
                int[] cur = q.poll(); 
                for(int d=0; d<4;d++){
                    int nr = dr[d] + cur[0];
                    int nc = dc[d] + cur[1];
                    if(nr>-1&&nc>-1&&nr<n&&nc<m&&!visited[nr][nc]&&maps[nr][nc]==1){
                        if(nr==n-1&&nc==m-1){
                            count++;
                            flag = true;
                            break loop;
                        }
                        visited[nr][nc] = true;
                        q.offer(new int[]{nr,nc});
                    }
                }//for_d END
            }//for_i END
        }// while_END
        
        if(flag) answer = count;
        
        
        return answer;
    }
}