https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net bfs를 통해 (0, 0)부터 (n-1, m-1)까지 이동하면 된다. 다음 노드가 방이면 이어서 이동하고, 다음 노드가 벽이면 부수고 이동한다. 즉, 큐에 벽을 부순 횟수도 담아주어야 한다. 그리고 벽을 부쉈을 때 굳이 1을 0으로 변경해줄 필요가 없으며, 방문처리만 해주면 된다. 중요한 점은 우선순위 큐를 사용해서, 벽을 부순 횟수가 적은 노드부터 꺼내야 한다는 것이다. 만..

https://www.acmicpc.net/problem/17182 17182번: 우주 탐사선 우주 탐사선 ana호는 어떤 행성계를 탐사하기 위해 발사된다. 모든 행성을 탐사하는데 걸리는 최소 시간을 계산하려 한다. 입력으로는 ana호가 탐색할 행성의 개수와 ana호가 발사되는 행성의 위 www.acmicpc.net 예를 들어 n이 3이고 시작점이 0일 때, (0 ➡️ 1로 가는 거리 + 0 ➡️ 2로 가는 거리)가 아닌 (0 ➡️ 1로 가는 거리 + 1 ➡️ 2로 가는 거리)가 더 짧을 수도 있다. 즉, 시작점에서 각 노드로 가는 거리만 최소로 갱신할 것이 아니라, 모든 노드에서 모든 노드로의 거리를 최소로 갱신하여 비교해야 한다. 따라서 플로이드 워셜을 사용해야 한다. 플로이드 워셜을 통해 map 배..