René's URL Explorer Experiment

{"@context":"https://schema.org","@type":"DiscussionForumPosting","headline":"p.g. 490의 '풀이 1 다익스트라 알고리즘 구현'","articleBody":"제가 가지고 있는 전자책은 2023년 10월 20일 버전 1.0 입니다.\r\n\r\np.g. 490의 '풀이 1 다익스트라 알고리즘 구현'의 풀이에 질문이 있어 문의 드립니다.\r\n\r\n본 풀이는 격자 모양을 사방이 거리 1인 노드로 연결된 그래프로 두고, 다익스트라 알고리즘으로 해결하고 있습니다.\r\n하지만 이는 적절하지 않은 풀이입니다.\r\n\r\n각 노드 사이의 거리가 1이기 때문에, 다익스트라 알고리즘으로 풀었을 때의 아무런 이점이 없습니다.\r\n동작 방식이 아래의 BFS코드와 완전히 동일하며, 유일한 차이는 우선순위큐의 유무이지만 우선순위큐를 사용하는 것이 아래의 이유로 손해입니다.\r\n\r\n- 특정 노드와 연결된 모든 모든 노드와의 거리가 동일하기 때문에 탐색의 우선순위가 없습니다.\r\n- 우선순위 큐를 사용하면 다음 탐색 후보 노드 삽입과 탐색 노드 추출에서 O(log n)으로 오히려 손해를 보게됩니다.\r\n  (BFS 풀이에서는 queue를 사용하므로 이과정이 O(1))\r\n\r\n아래와 같은 BFS 풀이가 더 적절한 풀이라고 생각합니다.\r\n```\r\nimport java.util.*;\r\n\r\nclass Solution {\r\n    int[] dx = {1, 0, -1, 0};\r\n    int[] dy = {0, 1, 0, -1};\r\n\r\n    public int solution(int[][] maps) {\r\n        return bfs(maps);\r\n    }\r\n\r\n    public int bfs(int[][] maps) {\r\n        Queue\u003cint[]\u003e queue = new LinkedList\u003c\u003e();\r\n        queue.add(new int[]{0, 0, 1});\r\n        maps[0][0] = 0;\r\n\r\n        while (!queue.isEmpty()) {\r\n            int[] current = queue.poll();\r\n            int curX = current[0];\r\n            int curY = current[1];\r\n            int depth = current[2];\r\n            if (curX == maps.length - 1 \u0026\u0026 curY == maps[0].length - 1) {\r\n                return depth;\r\n            }\r\n\r\n            for (int i = 0; i \u003c 4; i++) {\r\n                int nextX = curX + dx[i];\r\n                int nextY = curY + dy[i];\r\n\r\n                if (nextX \u003e= 0 \u0026\u0026 nextX \u003c maps.length \u0026\u0026 nextY \u003e= 0 \u0026\u0026 nextY \u003c maps[0].length \u0026\u0026 maps[nextX][nextY] == 1) {\r\n                    maps[nextX][nextY] = 0;\r\n                    queue.add(new int[]{nextX, nextY, depth + 1});\r\n                }\r\n            }\r\n        }\r\n        return -1;\r\n    }\r\n}\r\n```\r\n실제 프로그래머스의 효율성 테스트 결과 역시 차이가 있음을 확인하였습니다.\r\n\r\n1. 책에 기재된 다익스트라 풀이 코드\r\n![image](https://github.com/onlybooks/java-algorithm-interview/assets/67893559/cb81ba22-0f3a-4e64-a5ec-ba3a4a269f6c)\r\n\r\n2. BFS 풀이\r\n![image](https://github.com/onlybooks/java-algorithm-interview/assets/67893559/6f75b799-2eb7-4759-9093-196e744ba40a)\r\n\r\n검토 부탁드리며, 혹시 저의 의견중 틀린 부분이 있으면 알려주시면 감사하겠습니다.","author":{"url":"https://github.com/hoogom88","@type":"Person","name":"hoogom88"},"datePublished":"2024-02-14T04:48:06.000Z","interactionStatistic":{"@type":"InteractionCounter","interactionType":"https://schema.org/CommentAction","userInteractionCount":0},"url":"https://github.com/3/java-algorithm-interview/issues/3"}