[Programmers] 게임 맵 최단거리

난이도 : Level 2

문제링크

• 캐릭터가 상대 팀 진영까지 도착하기 위해 지나가야 하는 칸의 최소갯수를 리턴하라
• 캐릭터는 맨 좌측 상단에 위치한다
• 상대방 진영은 맨 우측 하단에 위치한다
• 게임 맵에서 벽은 지나갈 수 없다

 

해설

• 최소 비용 경로를 구해야 하기 때문에 BFS 탐색 알고리즘을 사용하여 푼다.
• 방문한 좌표들을 큐로 넣고 큐가 비어있지 않을 때까지 반복한다.
• 방문한 좌표에 지나온 칸 수를 같이 저장하고, 목표지에 도착시 그동안 저장했던 칸 수를 리턴한다.

import java.util.*;

class Solution {
    int[] dy, dx;
    boolean[][] visited;
        
    public int solution(int[][] maps) {
        int r_ = maps.length-1, c_ = maps[0].length-1;
        dy = new int[]{1, 0, -1, 0};
        dx = new int[]{0, 1, 0, -1};                
        
        Queue<int[]> queue = new LinkedList<>();        
        queue.offer(new int[] {0, 0, 1});
        visited = new boolean[r_+1][c_+1];
        visited[0][0] = true;
        
        while (!queue.isEmpty()) {
            int[] c = queue.poll();
            int cy = c[0], cx = c[1], ct = c[2];
            if (cy == r_ && cx == c_) {
                return ct;
            }

            for (int i = 0; i < 4; i++) {
                int ny = cy + dy[i];
                int nx = cx + dx[i];
                int nt = ct + 1;                
                             
                if (validate(ny, nx, maps)) {
                    queue.offer(new int[]{ny, nx, nt});
                    visited[ny][nx] = true;
                }
            }            
        }

        return -1;
    }
    
    private boolean validate(int y, int x, int[][] maps) {
        if (y < 0 || y > maps.length-1 || x < 0 || x > maps[0].length-1) {
            return false;
        }
        
        if (maps[y][x] == 0) {
            return false;
        }
        
        if (visited[y][x]) {
            return false;
        }
        
        return true;
    }
}

• 효율성 테스트 통과를 위해 primitive 타입 클래스를 사용해야 한다.
• class, hashset을 사용하면 통과되지 못한다.