[Programmers] 게임 맵 최단거리

❒ Description

---

제목	게임 맵 최단거리
링크	https://school.programmers.co.kr/learn/courses/30/lessons/1844
자료구조/알고리즘	Map, Queue / 넓이 우선 탐색(BFS)
시간 복잡도	O(row수 * col수)

 

BFS를 사용해서 해결 할 수 있는 문제이다. 문제의 핵심 포인트는 maps[row][col] 값을 업데이트 해주는 부분이다.

시간 복잡도의 경우는 모든 노드를 한 번씩 방문하기 때문에 O(N*M)의 시간 복잡도를 갖는다.

 

 

 

 

 

❒ Solution

---

import java.util.LinkedList;
import java.util.Queue;

class Solution {
    private final int[][] dirs = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
    private int maxCol;
    private int maxRow;
    private boolean[][] visited;

    public int solution(int[][] maps) {
        maxRow = maps.length;
        maxCol = maps[0].length;
        visited = new boolean[maxRow][maxCol];
        bfs(maps);
        boolean isVisitedEnemyHQ = visited[maxRow - 1][maxCol - 1];
        int enemyHQ = maps[maxRow - 1][maxCol - 1];
        return isVisitedEnemyHQ ? enemyHQ : -1;
    }

    public void bfs(int[][] maps) {
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{0, 0});
        visited[0][0] = true;
        while (!q.isEmpty()) {
            int[] cur = q.remove();
            int curRow = cur[0];
            int curCol = cur[1];

            for (int[] dir : dirs) {
                int nextRow = curRow + dir[0];
                int nextCol = curCol + dir[1];
                if (isInRange(nextRow, nextCol, maps) && isVisitable(nextRow, nextCol, maps)) {
                    visited[nextRow][nextCol] = true;
                    // ※ 방문 후 maps 값 업데이트
                    maps[nextRow][nextCol] = maps[curRow][curCol] + 1;
                    q.offer(new int[]{nextRow, nextCol});
                }
            }
        }
    }

    private boolean isInRange(int nextRow, int nextCol, int[][] maps) {
        return nextRow >= 0 && nextRow < maxRow && nextCol >= 0 && nextCol < maxCol;
    }
    
    private boolean isVisitable(int nextRow, int nextCol, int[][] maps) {
        return !visited[nextRow][nextCol] && maps[nextRow][nextCol] != 0;
    }
}

 

bfs 메소드에서 필요한 validation이 너무 많아서 isInRange와 isVisitable 메소드를 추출하였다.

 

 

 

 

 

---