oVeron

https://www.acmicpc.net/problem/23563 23563번: 벽 타기 출발하자마자 오른쪽으로 한 칸 이동하고, 위로 한 칸 벽을 타고 이동하면 총 1의 시간이 소요된다. www.acmicpc.net 벽을 타고 가는 시간과 일반적으로 이동하는 시간이 다르기 때문에, 일반적인 BFS 최단경로로 해결해서는 안 된다. 우리는목적지까지 이동하는 최단 경로를 알고 싶기 때문에 다익스트라로 해결하는 것이 가장 좋다. 이 문제의 핵심은 현재 위치에 벽이 존재하고 다음 위치에도 벽이 존재하면 0초로 이동할 수 있다는 것인데, 이를 쉽게 구현하기 위해 각 위치마다 주위에 벽이 있는지 미리 구한다(\(isAdjWall\)). 이렇게 하면 조건 하나만 추가하면 두 가지 경우로 나누어 쉽게 다익스트라를 구..

알고리즘/baekjoon 2023. 6. 5. 11:48