[알고리즘] 백준 2206

아래 정리하는 내용들은 대부분 다른 분들의 코드를 참고하여 작성한 코드이기 때문에 최적화 되어 있지 않으며 개인적으로 기억하기 위한 용도입니다. 혹시 문제 풀이를 위해서 검색하신 분들께서는 참고 수준으로만 읽어보시기 바랍니다. References https://swexpertacademy.com/ https://www.acmicpc.net/ https://leetcode.com/ 추천 블로그 https://zoosso.tistory.com/ 일반적인 최소 비용은 dijikstra 로 풀이하지만 이 문제의 경우에는 한칸 이동하는 비용이 동일하게 1 이기 때문에 BFS 를 사용한다. 아래 그림처럼 위로 이동하는 경우 1의 비용이 들지만 우회하는 경우 절대 더 작은 비용으로 방문하는 것이 불가하기 때문에 BFS 수행시 위 방향으로 이동을 먼저하도록 우선 큐에 넣어준다. 이 문제에서 또다른 핵심은 로켓을 사용해서 벽을 뚫고 방문했는지 사용하지 않은 상태에서 방문했는지를 추가적으로 관리해주는...

원문링크 : [알고리즘] 백준 2206