[프로그래머스] 게임 맵 최단거리 문제 (Java BFS 풀이)

안녕하세요.

오늘은 자바(Java)의 BFS를 이용한 프로그래머스 Lv.2 게임 맵 최단거리 문제를 풀어보겠습니다.

 

문제 설명

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

프로그래머스

게임 맵내에서 상대 팀 진영에 가장 빠르게 도달할 수 있는 거리(최단거리)를 계산하는 문제입니다.

움직일 때는 동, 서, 남, 북 방향으로만 한 칸씩만 이동할 수 있고, 게임 맵 크기를 벗어날 수는 없습니다.

 

예제 1) 예를 들어 이런 5x5 크기의 맵이 있다고 해봅시다.

예제 1

검은색 부분은 벽(막혀있는 길)이고, 흰색 부분은 갈 수 있는 길입니다.

또한 빨간색 부분(행 5, 열 5)이 상대팀 진영입니다. 상대팀 진영에 가장 빠르게 도달하기 위해서는 아래와 같이 이동해야 합니다.

예제 1 - 최단거리

노란색 블록들이 이동한 최단 거리입니다. 노란색 블록이 총 11개이므로, 11개의 칸을 지나서 상대 팀 진영에 가장 빠르게 도달했습니다.

 

<입출력>

• maps: [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]]
  • maps는 nxm 크기의 게임 맵. (n, m이 모두 1인 경우는 없음)
  • 0이 벽이 있는 자리, 1이 벽이 없는 자리
  • 처음에 캐릭터는 1행 1열에 위치, 상대방 진영은 n행 m열에 위치
• answer: 11

 

예제 2) 만약에 위와 같은 그림처럼 상대팀 진영에 도달할 수 없을 경우, -1을 return 하면 됩니다.

예제 2

<입출력>

• maps: [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]]
• answer: -1

 

풀이과정

우선 이 문제는 BFS를 이용하여 풀어야 하는 문제입니다.

DFS를 이용하게 되면, 게임 맵에서 끝까지(깊게) 내려가서 검색한 후, 처음으로 이동해서 다시 검색하는 과정을 거쳐야 하므로 효율성이 매우 낮습니다.

반면 BFS의 경우, Queue를 이용하여 게임 맵에서 (얕게 탐색하면서) 최단 거리를 계산하기 매우 좋습니다.

 

• 동서남북 탐색을 위해 dx, dy 배열을 사용하였습니다. 
• Queue : LinkedList
  • 처음 queue에 넣는 {0,0,1} 값: 0번째와 1번째 Index는 현재 검색 중인 x, y 좌표를, 2번째 Index는 cnt(현재까지 걸어온 거리)를 나타냅니다.
  • visited 배열: 해당 좌표를 이미 방문했는지 체크합니다. 처음에 (0,0)을 방문했으니, visited[0][0]을 true로 설정하였습니다.
  • queue가 비어있지 않을 때까지 while문을 반복합니다. (BFS)
    • 현재 좌표가 상대편 진영 (n-1, m-1)이라면 cnt(최단 거리)를 return 하게 됩니다.
    • 순차적인 동서남북 탐색을 위해 For문을 이용하여 x와 y값에 dx, dy의 현재 배열값을 더하였고 해당 nx, ny값이 0보다 크고 n, m보다 작으면서 maps[n][m]이 1(갈 수 있는 곳)이면서 visited 하지 않은 곳이라면, 다음에 탐색할 좌표의 visited를 true로 변경하고 queue에 추가하게 됩니다. 이때 cnt는 1 증가시켜, 현재까지 걸어온 거리를 업데이트해 줍니다.

import java.util.*;

class Solution {
    private static final int[] dx = {0, 0, -1, 1};
    private static final int[] dy = {-1, 1, 0, 0};
    
    public int solution(int[][] maps) {
        int n = maps.length;
        int m = maps[0].length;
        
        boolean[][] visited = new boolean[n][m];
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{0, 0, 1});
        visited[0][0] = true;
        
        while(!queue.isEmpty()){ // bfs
            int[] current = queue.poll();
            int x = current[0];
            int y = current[1];
            int cnt = current[2];
            
            if(x == n-1 && y == m-1){
                return cnt; // 최단 거리 반환 (bfs: 가장 처음 return 되는게 최단 거리)
            }
            
            for(int i=0;i<4;i++){
                int nx = x + dx[i];
                int ny = y + dy[i];
                
                if(nx >=0 && ny >= 0 && nx < n && ny < m && maps[nx][ny] == 1 && !visited[nx][ny]){
                    visited[nx][ny] = true;
                    queue.add(new int[]{nx, ny, cnt+1});
                }
            }
        }
        
        return -1;
    }
}

 

실행결과

프로그래머스 문제 실행결과 - 게임 맵 최단거리

• 모든 테스트를 성공적으로 통과하였습니다.

---

 

지금까지 자바(Java) BFS를 이용한 프로그래머스 '게임 맵 최단거리' 문제에 대해서 살펴보았습니다.

읽어주셔서, 감사합니다.