[백준/BOJ] 백준 2645번 : 회로배치

https://www.acmicpc.net/problem/2645 2645번: 회로배치 회로를 n×n의 격자 판에 배치하려고 한다. 여기서 각 격자(정사각형 칸)는 가장자리에 있는 격자를 제외하고 상, 하, 좌, 우 4개의 이웃 격자를 갖는다. 회로는 시작과 끝이 있는 연속된 이웃 격자 www.acmicpc.net 이미 회로가 놓인 위치를 2차원 배열에 표시해 놓고, 다익스트라 알고리즘을 통해 시작 지점부터 도착 지점까지 도달하는데 최소비용을 계산했다. 이때 최소비용을 계산하면서, come_from[55][55] 에 해당 위치로 오기 전에 직전에 어떤 위치에 있었는지 저장해 놓고, 도착 지점까지 최소 비용 계산이 끝나면 come_from[55][55]을 이용해 도착지점부터 시작지점까지 거꾸로 확인하면서 ..

2023.03.21