반응형
1261
-
BOJ) 알고스팟 (1261 번)알고리즘/백준 2021. 1. 21. 18:22
알고스팟 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 문제 벽이 존재하는 미로에서 처음 위치 (0,0)를 시작으로 (n-1,m-1)까지 도착해야한다. 이 때, 최소한으로 벽을 부시면서 경로를 찾는 문제다. 최소 + 경로 => 다익스트라를 이용하면 되겠다고 판단했다. 풀이 풀이는 간단하다. 일반적인 다익스트라를 구현하는 것 처럼 우선순위 큐를 활용해서 풀었다. 우선순위는 벽을 가장 적게 허문 순서대로 정렬했고, 이동하는 곳이 벽인 경우에는 +1을, 벽이 아닌 경우에는 +0을 해주며 길을..