[프로그래머스] 게임 맵 최단거리 (BFS) (너비우선탐색) (JAVA)

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

프로그래머스

---

문제 설명

ROR 게임은 두 팀으로 나누어서 진행하며, 상대 팀 진영을 먼저 파괴하면 이기는 게임입니다. 따라서, 각 팀은 상대 팀 진영에 최대한 빨리 도착하는 것이 유리합니다.

지금부터 당신은 한 팀의 팀원이 되어 게임을 진행하려고 합니다. 다음은 5 x 5 크기의 맵에, 당신의 캐릭터가 (행: 1, 열: 1) 위치에 있고, 상대 팀 진영은 (행: 5, 열: 5) 위치에 있는 경우의 예시입니다.

위 그림에서 검은색 부분은 벽으로 막혀있어 갈 수 없는 길이며, 흰색 부분은 갈 수 있는 길입니다. 캐릭터가 움직일 때는 동, 서, 남, 북 방향으로 한 칸씩 이동하며, 게임 맵을 벗어난 길은 갈 수 없습니다.
아래 예시는 캐릭터가 상대 팀 진영으로 가는 두 가지 방법을 나타내고 있습니다.

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

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

위 예시에서는 첫 번째 방법보다 더 빠르게 상대팀 진영에 도착하는 방법은 없으므로, 이 방법이 상대 팀 진영으로 가는 가장 빠른 방법입니다.

만약, 상대 팀이 자신의 팀 진영 주위에 벽을 세워두었다면 상대 팀 진영에 도착하지 못할 수도 있습니다. 예를 들어, 다음과 같은 경우에 당신의 캐릭터는 상대 팀 진영에 도착할 수 없습니다.

게임 맵의 상태 maps가 매개변수로 주어질 때, 캐릭터가 상대 팀 진영에 도착하기 위해서 지나가야 하는 칸의 개수의 최솟값을 return 하도록 solution 함수를 완성해주세요. 단, 상대 팀 진영에 도착할 수 없을 때는 -1을 return 해주세요.

제한사항

• maps는 n x m 크기의 게임 맵의 상태가 들어있는 2차원 배열로, n과 m은 각각 1 이상 100 이하의 자연수입니다.
  • n과 m은 서로 같을 수도, 다를 수도 있지만, n과 m이 모두 1인 경우는 입력으로 주어지지 않습니다.
• maps는 0과 1로만 이루어져 있으며, 0은 벽이 있는 자리, 1은 벽이 없는 자리를 나타냅니다.
• 처음에 캐릭터는 게임 맵의 좌측 상단인 (1, 1) 위치에 있으며, 상대방 진영은 게임 맵의 우측 하단인 (n, m) 위치에 있습니다.

---

※ JAVA 코드 (게임 맵 최단거리)

import java.io.*;
import java.util.*;

class Solution {
    static int N, M, dap;
    static int[][] map;
    static boolean[][] visited;
    
    // 동서남북 이동 루트
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};
    
    // 좌표를 담을 클래스
    public static class Node {
        int x, y;
        
        public Node(int x, int y){
            this.x = x;
            this.y = y;
        }
    }
    
    public static void bfs(int x, int y) {
        Queue<Node> q = new LinkedList<>();
        
        // 큐에 초기값 삽입
        q.offer(new Node(x, y));
        
        // 방문체크
        visited[x][y] = true;

        // 큐가 빌때까지 반복
        while(!q.isEmpty()){
            Node now = q.poll();
            for(int i = 0; i < 4; i++){
                int nx = now.x + dx[i];
                int ny = now.y + dy[i];

                // 이동시 맵의 범위를 벗어나지 않게 한다.
                if(nx < 0 || ny < 0 || nx >= N || ny >= M){
                    continue;
                }
                // 이동경로에 장애물이 있거나 이미 방문한 곳이라면 방문하지 않는다.
                if(map[nx][ny] == 0 || visited[nx][ny] == true) {
                    continue;
                }
                
                // 방문 체크
                q.offer(new Node(nx, ny));
                visited[nx][ny] = true;
                map[nx][ny] = map[now.x][now.y] + 1;
            }
        }
    }
    
    public int solution(int[][] maps) {
        int answer = 0;
        
        N = maps.length;
        M = maps[0].length;
        
        map = new int[N][M];
        visited = new boolean[N][M];
        
        for(int i = 0; i < N; i++){
            for(int j = 0; j < M; j++){
                map[i][j] = maps[i][j];
            }
        }
        
        bfs(0, 0);
        
        answer = map[N-1][M-1] == 1 ? -1 : map[N-1][M-1];
        
        return answer;
    }
}

---

※ 생각정리 (게임 맵 최단거리)

프로그래머스와 백준의 가장 큰 차이점은 Input값을 직접 입력하느냐 아니냐이다. 백준을 풀다가 프로그래머스 문제를 풀다보면 이런 점이 매우 헷갈린다.. 

문제자체는 아주 쉬웠지만 (전형적인 미로탐색 문제이기때문에) 입력방식에 되게 애를 먹었던 문제이다.

 

1. 초기화

- static형으로 맵 배열과 방문체크할 2차원 배열을 만들어 두었다.

- 전역변수 N, M에 파라미터로 들어온 maps를 읽어 세로, 가로 길이를 담아두었다.

- map 배열에 파라미터 값을 담아두었다. (사실 파라미터 배열을 그대로 사용해도 되지만 여러 테스트용도로 map을 사용했다.)

 

2. 탐색

- 문제에서 주어진 탐색은 1, 1부터 시작한다라는 문구가 매우 헷갈렸다. 백준에서는 경우에 따라 0, 0 좌표에서 탐색을 하기도 하고 1, 1에서 탐색을 하기도 한다. 그래서 처음에는 배열의 크기를 N+1, M+1로 만들어두었다. 나중에 입력값이 0, 0 좌표부터 찍힌다는 것을 발견하고 이점을 수정하였다.

- 탐색이 돌면서 이동전 좌표의 값을 다음 좌표에 값에 + 1하여 담는 방식으로 진행하였다. 이때 중요한 점은 장애물이 있는 지점과 맵의 범위 방문체크를 해주어야한다는 것이다. (방문체크를 하지 않을시 최악은 사이클이 발생해 무한루프에 빠질 수 있다.

- 위에 속하지 않는 다음 좌표는 큐에 담아두고 방문체크를 해준다.  

3. 출력

- 이 문제의 핵심은 1) 도착지점에 갔느냐 안갔느냐, 2) 만약 갔다면 몇번 이동했느냐 이다.

- 1)번을 위해 map[N-1][M-1] 지점의 값이 그대로 인지 아니면 변화했는지를 확인하였다.

- 2)번은 변화했다면 해당 값을 출력해주었다.

 

- 새벽코딩 -