경로찾기 > 문제은행

본문 바로가기


문제은행

1008 : 경로찾기

제한시간: 1000 ms    메모리제한: 128 MB
해결횟수: 233 회    시도횟수: 3154 회   



경완이와 진욱이는 학교에서 수업을 들은 뒤 점심을 먹으러 나갔다.
학교는 가로 n칸 세로 n칸으로 이루어져 있으며 이 중 몇몇 칸에는 건물이 있어 이동할 수 없다.
아래 그림 1에서 회색으로 표시된 부분이 건물 빨간색으로 표시된 부분이 출발점 파란색으로 표시된 부분이 도착점이다.
건물과 출발점 도착점을 제외한 모든 칸에는 일사량이 자연수로 주어져 있다.

 

밖의 날씨가 매우 덥기 때문에 경완이와 진욱이는 일사량들의 합이 최소가 되는 경로로 이동하려고 한다.

 

예를 들어 그림 2와 같이 이동하면 일사량의 합이 23이지만 그림 3과 같이 이동하면 일사량의 합이 14로 최소가 된다.

 

e3050b66a1b29a01767400d7560a4131_1449724
 

그런데 식당은 t분 후에 문을 닫으므로 경완이와 진욱이는 t분 내로 식당에 도착해야한다.
단 격자 1칸을 이동하는 데는 1분이 걸린다. 그러므로 위 그림 2와 같이 이동하는 데는 6분 그림 3과 같이 이동하는 데는 10분이 걸린다.
만약 t = 9라면 그림 3과 같이 이동할 수 없으며 따라서 그림 4의 경로를 선택하는 것이 일사량 최소로 한다.

 

학교의 크기 n과 각 칸에서의 일사량과 시간 t가 주어졌을 때 시간 내로 이동할 수 있으면서 일사량들의 합을 최소로 하는 프로그램을 작성하여라.


첫 번째 줄에 자연수 n(2≤n≤100)과 t(1≤t≤5000)의 값이 주어진다. 두 번째 줄에서 차례로 n개의 줄에는 각각의 격자에 대한 정보가 공백으로 구분되어 입력한다. 이 때 0은 건물 -1은 출발점 -2는 도착점을 의미하며 나머지 칸에는 일사량을 나타내는 10,000 이하의 자연수가 적혀 있다.



첫 번째 줄에 가능한 일사량 합의 최솟값을 출력한다. 시간 내로 출발점에서 도착점까지 이동하는 것이 불가능하면 -1을 출력한다.


[Copy]
6 9
4 1 -1 4 2 0
1 2 0 0 7 1 
1 5 4 2 8 2
2 1 1 0 2 2
0 0 3 2 -2 1
1 1 4 7 6 1
[Copy]
15





HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.