[PGS] 게임 맵 최단거리 - JAVA

💡 문제

💬 입출력 예시

📌 풀이(소스코드)

import java.util.*;

class Solution {
    
    static int min = Integer.MAX_VALUE;
    
    static final int[] dr = {-1, 1, 0, 0};
    static final int[] dc = {0, 0, -1, 1};
    
    static boolean[][] used;
    
    public int solution(int[][] maps) {
        int n = maps.length;
        int m = maps[0].length;
        
        used = new boolean[n][m];
        
        bfs(n, m, maps);
        
        if (isReachable(min)) {
            return min;
        }
        
        return -1;
    }
    
    private void bfs(int n, int m, int[][] maps) {
        Queue<Pos> q = new LinkedList<>();
        q.offer(new Pos(0, 0, 1));
        used[0][0] = true;
        
        while (!q.isEmpty()) {
            Pos now = q.poll();
            int r = now.r;
            int c = now.c;
            int cnt = now.cnt;
            
            if (isDestination(r, c, n-1, m-1)) {
                min = Math.min(min, cnt);
            }
            
            for (int i = 0; i < 4; i++) {
                int nr = r + dr[i];
                int nc = c + dc[i];
                
                // 범위 밖
                if (isOutOfRange(nr, nc, n, m)) {
                    continue;
                }
                // 이동할 수 없는 경우
                if (isImpossible(used[nr][nc], maps[nr][nc])) {
                    continue;
                }
                // 이동가능한 경우
                used[nr][nc] = true;
                q.offer(new Pos(nr, nc, cnt + 1));
            }
        }
    }
    
    private boolean isReachable(int value) {
        return value != Integer.MAX_VALUE;
    }
    
    private boolean isDestination(int r, int c, int n, int m) {
        return r == n && c == m;
    }
    
    private boolean isOutOfRange(int r, int c, int n, int m) {
        return r < 0 || c < 0 || r >=n || c >= m;
    }
    
    private boolean isImpossible(boolean b, int n) {
        return b || n == 0;
    }
    
    class Pos {
        int r;
        int c;
        int cnt;
        
        public Pos(int r, int c, int cnt) {
            this.r = r;
            this.c = c;
            this.cnt = cnt;
        }
    }
}

📄 해설

접근

• BFS 유형 중 플러드필이라는 문제 유형의 기본문제이다.
• 해당 유형을 잘 알고 있다면 쉽게 해결 가능하다.
• 다음과 같은 접근으로 시작한다.
  • 캐릭터를 이동시켜보면서 이동 칸수를 센다.
  • 현재 위치가 적 팀 진영인지 확인하고, 적 팀 진영이라면 이동 칸수의 최솟값을 갱신한다.
  • 최솟값이 갱신되었다면 적 팀 진영까지 이동 가능. 갱신이 안 됐으면 이동 불가능

과정

• n x m 크기의 방문 배열을 생성하고, BFS 탐색을 수행한다. 시작 위치는 [0, 0] 으로 고정
  • n : maps 배열의 행 개수, m : maps 배열의 열 개수
• BFS 탐색은 아래 과정과 같이 이루어진다.
  • 큐에 시작점을 넣고 방문처리 후 탐색을 시작한다.
  • 큐가 빌때까지 노드를 빼고 넣으며 진행한다.
  • 현재 칸이 적 팀 진영 [n-1, m-1] 인지 확인하고, 적 팀 진영이면 최솟값을 갱신한다.
  • 동서남북으로 이동가능한 칸을 찾는다. (범위를 벗어나지 않고, 방문하지 않았고, 벽이 아닌 칸이 이동 가능한 칸)
  • 이동가능하면 해당 칸을 큐에 넣고 방문처리를 한다. 이때 cnt 값을 증가시켜서 이동횟수를 센다.