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

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

프로그래머스

 

풀이방법

사용된 것:

BFS

 

 

 

 

 

2025.03.28

BFS 문제이다.

각 칸의 정보는 길이가 3인 int 배열로 표현할 수 있다.

이 배열의 요소들은 각각 {행 인덱스, 열 인덱스, 출발점에서 해당 칸까지 오는 동안 거쳐온 칸 수}

따라서, Queue<int[]>를 사용해 BFS를 구현하면 된다.

 

answer의 값을 -1로 초기화한다.

목적지에 도달하는 순간, 그곳까지 오는 동안 거쳐온 칸 수를 answer에 넣어준다.

 

BFS가 끝난 후 answer을 리턴해준다.

만약 목적지에 도착하지 못하는 경우라면, answer의 값이 변경되지 않으므로 문제의 요구사항대로 -1을 리턴할 수 있다.

 

코드

Java(2025.03.28)

import java.util.*;

class Solution {
    public int solution(int[][] maps) {
        int n = maps.length-1;  // 목적지의 i 인덱스
        int m = maps[0].length-1;   // 목적지의 j 인덱스
        int[] moveI = {0, 0, 1, -1};
        int[] moveJ = {1, -1, 0, 0};
        
        boolean[][] visited = new boolean[n+1][m+1];
        
        // BFS 수행
        Queue<int[]> q = new LinkedList<int[]>();   // 요소의 값은 차례대로 i, j, 해당 지점까지 방문한 칸 수
        q.add(new int[]{0, 0, 1});
        
        int answer = -1;
        while(!q.isEmpty()) {
            int[] cur = q.poll();
            int i = cur[0];
            int j = cur[1];
            int dis = cur[2];
            
            if(i<0||j<0||i>n||j>m) continue;
            if(visited[i][j]) continue;
            if(maps[i][j] == 0) continue;
            
            // 적진에 도착한 경우
            if (i==n && j==m) {
                answer = dis;
                break;
            }
            
            visited[i][j] = true;
            // 동서남북 이동
            for(int d=0; d<4; d++) {
                q.add(new int[]{i+moveI[d], j+moveJ[d], dis+1});
            }
        }
        
        return answer;
    }
    
}