2665. 미로 만들기
브이담곰
https://www.acmicpc.net/problem/2665✔ 유형 : 다익스트라✔ 문제 풀이: 문제에서 구하고자 하는 것은 최단 거리가 아니라 검은 방을 최대한 적게 지나야 하는 것이다.시작방에서 출발하여 길을 찾아서 끝방으로 가는 것이 목적인데,/ 아래 그림의 경우에는 시작방에서 끝 방으로 갈 수가 없다. 부득이 검은 방 몇 개를 흰 방으로 바꾸어야 하는데 되도록 적은 수의 방의 색을 바꾸고 싶다.문제에 흰 방에 대한 최소 기준이 없다. 이 문제의 목표는 1. 처음에서 끝으로 도달2. 검은 방을 적게 거침 다익스트라 : 하나의 시작점으로부터 다른 모든 정점까지의 최단거리를 구하는 알고리즘. 다익스트라 알고리즘을 이용하여 최단거리 = 검은방으로 바꾼 횟수로 문제를 해결하면 된다. 코드import ..