[programmers] 게임 맵 최단거리 - Java

게임 맵 최단거리

문제 설명

• 첫 번째 방법은 11개의 칸을 지나서 상대 팀 진영에 도착했습니다.

• 두 번째 방법은 15개의 칸을 지나서 상대팀 진영에 도착했습니다.

제한사항

• maps는 n x m 크기의 게임 맵의 상태가 들어있는 2차원 배열로, n과 m은 각각 1 이상 100 이하의 자연수입니다.
• n과 m은 서로 같을 수도, 다를 수도 있지만, n과 m이 모두 1인 경우는 입력으로 주어지지 않습니다.

• maps는 0과 1로만 이루어져 있으며, 0은 벽이 있는 자리, 1은 벽이 없는 자리를 나타냅니다.

• 처음에 캐릭터는 게임 맵의 좌측 상단인 (1, 1) 위치에 있으며, 상대방 진영은 게임 맵의 우측 하단인 (n, m) 위치에 있습니다.

입출력 예

입출력 예 설명

solution.java

import java.util.*;

class Solution {
    
    static class Node {
        int x, y, dist;

        Node(int x, int y, int dist) {
            this.x = x;
            this.y = y;
            this.dist = dist;
        }    
    }
    
    public int solution(int[][] maps) {
        int n = maps.length;
        int m = maps[0].length;

        // 네 방향으로 탐색하기 위한 방향 배열
        int[] dx = {0, 0, 1, -1};
        int[] dy = {1, -1, 0, 0};

        Queue<Node> queue = new LinkedList<>();
        boolean[][] visited = new boolean[n][m];

        queue.offer(new Node(0, 0, 1));
        visited[0][0] = true;

        while (!queue.isEmpty()) {
            Node node = queue.poll();

            // 적 팀 진영에 도착했는지 확인
            if (node.x == n - 1 && node.y == m - 1) {
                return node.dist;
            }

            // 네 방향 모두 탐색
            for (int i = 0; i < 4; i++) {
                int nx = node.x + dx[i];
                int ny = node.y + dy[i];

                // 다음 이동 위치가 벽이 아니고, n * m 배열 내에 있고, 방문하지 않았는지 확인
                if (nx >= 0 && nx < n && ny >= 0 && ny < m && maps[nx][ny] == 1 && !visited[nx][ny]) {
                    queue.offer(new Node(nx, ny, node.dist + 1));
                    visited[nx][ny] = true;
                }
            }
        }

        // 적 진영까지 도달하지 못할 경우
        return -1;
    }
}

핵심 키워드

• BFS를 구현하기 위해 Queue를 사용한다.
• BFS는 레벨별로 노드를 탐색하므로 다음 레벨의 노드로 이동하기 전에 현재 레벨의 모든 노드를 탐색해야 한다.
• 따라서 FIFO의 순서를 가지는 Queue 로 구현할 수 있다.

문제 풀이

• Node 클래스
• x 위치, y 위치, 출발점에서의 거리를 담고 있는 정적 클래스를 선언한다.

• 변수 초기화
• n과 m은 지도의 크기를 나타낸다.
• dx와 dy는 오른쪽, 왼쪽, 아래, 위의 네 방향을 나타내는 배열이다.
• queue는 BFS 순회에 사용되는 FIFO 큐이다.
• visited는 방문한 노드를 추적하기 위한 2차원 부울 배열이다.

• BFS 순회
• 시작 노드 [0,0] 를 거리 1로 대기열에 추가하는 것으로 시작한다.
• 대기열에서 노드를 꺼내서 네 방향에서 인접 노드를 탐색하는 루프에 들어간다.
• 인접 노드가 유효한 경우(벽이 아닌 경계 내, 방문하지 않은 경우) 거리를 증가시켜서하여 대기열에 추가하고, 방문여부를 표시한다.
• 상대 진영에 도달하거나 더 이상 탐색할 노드가 없을 때까지 반복한다.

• 상대 캠프에 접근할 수 없는 경우
• 상대 진영에 도달하지 못한 채 루프가 완료되면 -1을 반환한다.

결론!