Programmers 게임 맵 최단거리

 

- 목차

 

소개.

아래는 Programmers 의 게임 맵 최단거리 문제의 웹링크입니다.

 

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

프로그래머스

 

 

문제 풀이.

캐릭터가 시작점인 (0,0) 에서 목적지인 (m,n) 까지의 최단거리를 구하는 문제입니다.

최단거리를 구하기 위해서 그래프 탐색 알고리즘을 사용합니다.

저는 BFS 를 사용하였구요.

BFS 로 탐색하는 과정에서 maps 에 해당하는 배열에 이동거리 값을 업데이트하였습니다.

 

< 알고리즘 >

import java.util.*;

class Solution {

  public int solution(int[][] maps) {

    // 목적지까지 도달할 수 있는 방법이 없다면 -1 를 반환합니다.
    int answer = -1;

    // 게임 맵에서 캐릭터가 이동할 수 있는 모든 방향들입니다. 
    int[] dx = new int[]{1, 0, -1, 0};
    int[] dy = new int[]{0, -1, 0, 1};
    
    // 게임 맵의 크기 정보입니다. 
    int height = maps.length;
    int width = maps[0].length;
    
    // 그래프 탐색을 위한 visited 배열입니다. 
    boolean[][] visited = new boolean[height][width];
    
    // 시작 위치와 목적지 위치 정보입니다. 
    int[] start = new int[]{0, 0};
    int[] destination = new int[]{height - 1, width - 1};

    // BFS 를 위한 Queue 입니다. 
    Queue<int[]> queue = new LinkedList<>();
    
    // 시작점인 (0, 0) 을 Queue 에 삽입합니다. 
    // 그리고 방문 배열은 변경합니다. 
    queue.add(start);
    visited[start[0]][start[1]] = true;

    while (!queue.isEmpty()) {
      int[] curPosition = queue.poll();
      int curX = curPosition[1];
      int curY = curPosition[0];

      // 캐릭터가 목적지에 도달하게 되면 탐색을 종료합니다. 
      // 각각의 게임맵에는 캐릭터가 이동한 값을 1씩 Increment 합니다. 
      // 목적지에 해당하는 게임맵 타일에 적힌 숫자가 곧 이동한 거리가 됩니다. 
      if (curY == destination[0] && curX == destination[1]) {
        answer = maps[destination[0]][destination[1]];
        return answer;
      }

      for (int i = 0; i < 4; i++) {
        int nextY = curY + dy[i];
        int nextX = curX + dx[i];
        
        // 탐색을 종료하는 조건들
        if (nextY >= height) continue;
        if (nextX >= width) continue;
        if (nextY < 0) continue;
        if (nextX < 0) continue;
        if (visited[nextY][nextX]) continue;
        if (maps[nextY][nextX] == 0) continue;
        
        queue.add(new int[]{nextY, nextX});
        maps[nextY][nextX] = maps[curY][curX] + 1;
        visited[nextY][nextX] = true;
      }
    }

    return answer;
  }

}