p1844.md

1844. 게임 맵 최단거리

Summary

🙇‍♂️ URL : https://programmers.co.kr/learn/courses/30/lessons/1844
🤷‍♂️ Difficulty: ?
💆‍♂️ Submissions : Success

Source code

class Solution_BFS {
    public int solution(int[][] maps) {
        int answer = 0;

        int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        int[][] steps = new int[maps.length][maps[0].length];

        for (int i = 0; i < steps.length; i++) {
            for (int j = 0; j < steps[i].length; j++) {
                // 모든 경로를 -1로 해두고 최종 반환값을 목적지로 해주면,
                // 만약 목적지까지 이동하지 못하는 경로라 하더라도
                // -1을 바로 뽑아낼 수 있음!
                steps[i][j] = -1;
            }
        }

        // 이동하는 모든 곳은 Queue에 넣고, 하나씩 빼면서 주변의 좌표들로 이동한다.
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{0, 0});
        steps[0][0] = 1;  // 출발지를 1로 세팅(한걸음 이동함)

        while (!queue.isEmpty()) {
            int[] point = queue.poll();
            for (int[] dir : dirs) {
                int row = point[0] + dir[0]; // row좌표: 큐에서 뽑인 행렬 중 0번째
                int col = point[1] + dir[1]; // col좌표: 큐에서 뽑인 행렬 중 1번째
                if (row >= 0 && col >= 0 && row < maps.length && col < maps[0].length) {
                    if (maps[row][col] == 1 && steps[row][col] == -1) { // 갈수 있는데 아직 안갔다면?
                        // 현재 좌표까지 온 이동횟수 + 1 -> 다음번 이동할 좌표까지 이동할 횟수
                        steps[row][col] = steps[point[0]][point[1]] + 1;
                        // 다음번 이동할 좌표를 큐에 넣어줌 -> while문에 의하여 계속 반복해서 이동!
                        queue.offer(new int[]{row, col});
                    }
                }
            }
        }
        return steps[maps.length - 1][maps[0].length - 1];
    }
}

How to Approach

특정 위치로의 이동은 BFS 또는 DFS 알고리즘을 사용해야 한다고 배웠는데, 각 알고리즘 별로 장단점이 있다.

1. BFS: 해당 경로로의 최단 거리 계산이 가능

2. DFS: 해당 경로로 갈 수 있는 모든 경우의 수 계산이 가능

본 문제는 최단 거리 계산이 목적이므로 BFS를 사용하는 것이 좋지만, 처음 문제를 접할 당시 BFS가 익숙하지 않았더터라(DFS로 풀면서 BFS라고 착각한 것도 한몫 했었음) DFS 형식으로 문제를 풀었고 결국 효율성 실패를 맛보았다.

class Solution_DFS {
    public int solution(int[][] maps) {
        int answer = 0;
        /*발도장맵*/  boolean[][]     visited = new boolean[maps.length][maps[0].length];
        /*방향지시등*/   int[][]         dirs    = {{-1,0}, {1,0}, {0,-1}, {0,1}};
        /*이동횟수리스트*/ List<Integer>   countList = new ArrayList<>();

        dfs(maps, visited, dirs, countList, 0, 0, 0);

        if (countList.size() == 0) {
            // 목적지로 이동한 적이 한번도 없을 때 -> 이동이 불가능할 때
            answer = -1;
        } else {
            // 목적지로 이동할 때까지의 걸음 횟수 중 가장 작은 값 반환
            Collections.sort(countList);
            answer = countList.get(0);
        }
        return answer;
    }

    public void dfs(int[][] maps, boolean[][] visited, int[][] dirs, List<Integer> countList, int _row, int _col, int count) {

        // 목적지에 도달하면 -> 이동할때까지 걸린 횟수를 리스트에 넣어주고 리턴
        if (_row == maps.length-1 && _col == maps[0].length-1) {
            countList.add(count+1);
            return;
        }
        for (int i=0; i<dirs.length; i++) {
            int row = _row + dirs[i][0];    // 방향지시등(row이동)
            int col = _col + dirs[i][1];    // 방향지시등(col이동)
            if (row >= 0 && col >= 0 && row < maps.length && col < maps[0].length) {
                if (maps[row][col] == 1 && !visited[row][col]) {
                    visited[row][col] = true;   // 여기는 왔던 곳이니까 발도장 찍기
                    dfs(maps, visited, dirs, countList, row, col, count + 1);
                    visited[row][col] = false;  // 왔던길을 다시 되돌아가봐야하니까 발도장 다시 없애기
                }
            }
        }
        return;
    }
}

위의 DFS 소스를 가지고 체점을 하면 문제는 모두 풀어내지만 효율성에서는 통과가 되지 않았다. 아무래도 DFS 방식의 특성 상 모든 경로를 다 계산해버리기 때문에 맵의 크기가 커질수록 소요되는 시간이 증가해서 그런 것이라고 생각했다.

목적지로 이동하는 중 갈랫길이 나오는 경우, DFS는 해당 갈랫길로부터 목적지까지 한번 이동해보고 다시 갈랫길로 돌아와 다른 경로로 목적지까지 가는 '깊이 쭉 들어갔다 나오는 방식'이라면, BFS는 갈랫길과 상관없이 '출발지로부터 해당 경로까지 몇걸음인지'만 계속 적어주면서 목적지까지 가는 방식이 된다.

그러므로 갈랫길이 많은(들어갔다 나와야 하는 길이 많은) 복잡한 맵일수록 DFS는 시간이 많이 소요되지만, BFS는 갈랫길과 크게 상관없이 목적지까지의 이동 횟수를 바로 얻을 수 있다.