다익스트라 알고리즘14 [백준] 1261번 - 알고스팟 [Java] https://www.acmicpc.net/problem/1261 1. 아이디어 다익스트라 알고리즘 또는 0-1 BFS 알고리즘으로 해결할 수 있다.2. 문제풀이 (1, 1)에서 (N, M)까지 벽을 최소한으로 부수면서 이동해야 하는 문제로 벽이 있는 칸을 가중치 1인 간선으로 이동, 벽이 없는 칸은 가중치 0인 간선으로 이동이라고 했을 때 0과 1의 가중치를 갖는 간선으로 이루어진 그래프에서 최단 경로로 이동하는 문제가 된다. 이는 다익스트라 알고리즘으로 해결할 수 있고 가중치가 0과 1 두가지만 있는 경우 Deque 자료구조를 활용한 0-1 BFS 알고리즘으로도 해결할 수 있다. 두 가지 모두 간단하게 구현만하면 해결할 수 있다.3. 코드 import java.io.*;import java.util.. 2025. 2. 1. [백준] 13549번 - 숨바꼭질 3 [Java] https://www.acmicpc.net/problem/13549 1. 아이디어 이전 숨바꼭질 문제에서 2*X 위치로는 이동 시간 없이 움직일 수 있는 경우로 다익스트라 알고리즘과 0-1 BFS 알고리즘을 활용해서 해결할 수 있다.([코딩테스트 준비/백준] - [백준] 1697번 - 숨바꼭질 [Java])2. 문제풀이 - 다익스트라 알고리즘수빈이의 위치에서 동생의 위치로 가는 최단 경로로 각 간선의 가중치가 다르기에 다익스트라 알고리즘을 적용하면 해결할 수 있다. 위치와 이동하는데 걸렸던 시간을 갖는 Node 클래스를 활용해서 구현했다. - 0-1 BFS각 간선의 가중치가 0과 1 두가지여서 0-1 BFS 알고리즘으로도 해결할 수 있었다. 일반적인 최단거리 BFS 구현에서 Queue 대신 Deque를.. 2025. 1. 22. 이전 1 2 다음
