[백준 / BOJ] 20046 Road Reconstruction

문제

출처 : www.acmicpc.net/problem/20046

20046번: Road Reconstruction

m*n의 격자 모양의 격자가 있다. 격자의 각 칸에는 도로가 있을수도, 없을수도 있는데, 이 격자에 도로를 배치하여 (1,1)지점에서 (m,n)까지 가는 다리를 만들어야한다.

 

칸마다 도로를 만드는데 드는 비용은 다르다 (비용 1과 비용2가 있음)

-1인 지점에는 도로를 만들지 못하고, 0은 이미 도로가 있는 곳이다.

비용을 최소한으로 사용해서 도로를 만드는경우를 구해야한다.

 

풀이

2020 ICPC문제였다. 다익스트라를 사용해 풀면된다.

 

check[][]배열을 만들고, 

(1,1)지점에서 시작해서 (m,n)까지 가는 경로에서 해당 칸을 갔을때, 드는 최솟값을 저장해준다.

예를들어, (1,1)에서 (2,3) 지점까지 갔을때의 최솟값을 check[2][3]에 저장해줌

pq와 너비우선 탐색방식을 사용했기때문에, 가장 처음 m,n에 도착했을때가 무조건 최솟값이다. 따라서, 처음 m,n에 도착했다면 (m,n)으로 가는 다른경로를 봐주지않고, 바로 탐색을 종료해줘야한다.

이렇게하면, 탐색이 끝났을때, check[m][n]에 저장된값이 답이다.

 

시작지점(1,1)이 -1 이거나 도착지점(m,n)이라면 어떻게 해도 (1,1)에서 (m,n)까지 연결되는 다리를 만들수없어서 -1 을 출력해야하는 것에 유의하자

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/20046%20Road%20Reconstruction/main.cpp

devxb/JJUNalgo