[프로그래머스/1844] 게임 맵 최단거리 (Java)

Question

찾아라 프로그래밍 마스터 > 게임 맵 최단거리

• 문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/1844
• 분류 : BFS
• 풀이 시간 : 20분

문제 해설

1. 상대 팀 진영까지 먼저 도착해야함 : N x M 크기의 행렬인 맵 존재
2. 내 캐릭터는 맵의 (0, 0)에 위치해있음
3. 상대 팀 진영은 (N - 1, M - 1)에 위치해있음
4. 검은색 부분(0) = 벽이기 때문에 움직일 수 없음, 칀색 부분(1)으로만 이동 가능
5. 캐릭터는 한번에 동서남북 방향으로만 이동 가능
6. 상대팀 진영까지 가장 빠르게 이동할 수 있는 횟수는?
7. 상대팀까지 움직일 수 없으면 -1 리턴

Solution

풀이 접근 방법

1. 특정 좌표까지 제일 빠르게 가는 방법 + 동서남북으로 이동 = BFS

2. 방문체크와 해당 칸까지 몇번째로 이동했는지 알기 위해 int[][] visited 사용

   1. visited[x][y] == 0 : 아직 방문 안함
   2. visited[x][y] != 0 : 방문 기록 존재, 해당 칸까지 오는데 몇번 움직였는지 저장되어있음

정답 코드

import java.util.*;
class Solution {
    class Node {
        int x, y;
        
        public Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    int N, M;
    public int solution(int[][] maps) {
        int answer = 0;
        N = maps.length;
        M = maps[0].length;
        
        return countRoute(maps);
    }
    
    int countRoute(int[][] maps) {
        int[] dx = {0, 0, 1, -1}, dy = {1, -1, 0, 0};
        int[][] visited = new int[N][M];
        Queue<Node> queue = new LinkedList<Node>();
        
        // 시작점 초기화
        visited[0][0] = 1;
        queue.add(new Node(0, 0));
        
        while(!queue.isEmpty()) {
            Node current = queue.poll();
            // 현재 있는 칸에서 다음칸으로 이동했을 때 움직인 횟수
            int moveCount = visited[current.x][current.y] + 1;
            
            for (int i = 0; i < 4; i++) {
                int nx = current.x + dx[i];
                int ny = current.y + dy[i];
                
                // 맵 범위를 벗어났거나 벽이면 이동 불가
                if (!isIn(nx, ny) || maps[nx][ny] == 0)
                    continue;
                
                // 이미 방문한 적이 있으나 현재 움직인 값보다 더 적게 방문한 기록이 있으면 이동 불가
                if (visited[nx][ny] != 0 && visited[nx][ny] <= moveCount)
                    continue;
                
                // 방문한적이 없거나
                // 방문했지만 현재 좌표에서 이동했을때 더 빨리 도착할 수 있으면 새로 이동
                visited[nx][ny] = moveCount;
                
                // 상대팀 진영에 도착했으면 다음으로 이동 안함
                if (nx == N - 1 && ny == M - 1)
                    continue;
                
                queue.add(new Node(nx, ny));
            }
        }
        
        // 상대팀 진영으로 방문할 수 없으면 -1 리턴
        return visited[N-1][M-1] == 0 ? -1 : visited[N-1][M-1];
    }
    
    boolean isIn(int x, int y) {
        if (0 <= x && x < N && 0 <= y && y < M)
            return true;
        return false;
    }
}