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

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

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

문제 풀이 :

최단 거리를 구해야하기 때문에 BFS를 사용했습니다.

class Pair에 count 변수로 지나가는 칸의 개수의 최솟값을 넣어주었습니다.

BFS를 돌면서 좌표가 팀 진영에 도착했을 때는 count를 return 해줍니다.

도착하지 못했을 때에는 -1을 return 해줍니다.

import java.util.*;

class Solution2 {
    static int[][] dir = {{-1,0},{0,-1},{1,0},{0,1}};
    static boolean[][] visited;
    static int n,m;
    public static int solution(int[][] maps) {
        n = maps.length;
        m = maps[0].length;
        visited = new boolean[n][m];
        
        return bfs(0,0,maps);
        
    }
    public static int bfs(int x, int y, int[][] maps){
    	Queue<Pair> queue = new LinkedList();
        queue.add(new Pair(x,y,1));
        visited[x][y] = true;

        while(!queue.isEmpty()){
        	Pair p = queue.poll();
            if(p.x==n-1 && p.y==m-1) return p.count;
        	
            for(int k = 0; k< 4; k++){
                int nx = dir[k][0] + p.x;
                int ny = dir[k][1] + p.y;
                
                if(isInside(nx,ny) && !visited[nx][ny] && maps[nx][ny]==1){
                	visited[nx][ny] = true;
                    queue.add(new Pair(nx,ny,p.count+1));
                }
            }
        }
		return -1;
    }
    public static boolean isInside(int x, int y){
        return x>=0 && x<n && y>=0 && y<m;
    }
}

class Pair{
    int x;
    int y;
    int count;
    
    Pair(int x, int y, int count){
        this.x = x;
        this.y = y;
        this.count = count;
    }
}