미로만들기
-
[백준]2665: 미로만들기 - JAVA문제풀이/백준 2021. 4. 11. 15:44
[백준]2665: 미로만들기 www.acmicpc.net/problem/2665 2665번: 미로만들기 첫 줄에는 한 줄에 들어가는 방의 수 n(1≤n≤50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다. www.acmicpc.net 풀이 BFS + 다익스트라를 활용하여 풀었다. 첫 노드에서 오른쪽 아래 노드로 가는 최단 거리 중에서 검은색 벽을 가장 적게 바꾸는 방법의 횟수를 출력하는 문제로 이전에 풀었던 '벽 부수고 이동하기'와 유사한 문제였다. 검은색 벽을 흰색 벽으로 바꾸는 최소 횟수를 누적하여 계산하며 탐색하기 위해 다익스트라 방법을 사용하였다. dist배열을 사용하여 현재 위치의 가장 최소 횟수를 저장할 수 ..