119 구급대 > 문제은행

본문 바로가기


실전대비 Level2

1113 : 119 구급대

제한시간: 1000 ms    메모리제한: 64 MB
해결횟수: 190 회    시도횟수: 643 회   



철수네 동네의 소방서에서는 주민들의 편의를 위해 119 구급 대를 운영하고 있다. 가끔 일어나는 일이지만 위급한 일은 분초를 다투는 일이 많기 때문에 119 구급대가 위급한 일이 발생한 목표지점까지 최대한 빨리 도착해야 한다.

 

119 구급차는 성능이 좋아 일반 자동차보다 아주 빠른 속도로 주행할 수 있지만 코너를 돌 때에는 일반 자동차처럼 속도를 완전히 줄여야 하기 때문에 목표지점에 도달할 때 까지 되도록 코너를 돌지 않고 직선 도로를 통해 도착해야 시간을 줄일 수 있다.

 

e3050b66a1b29a01767400d7560a4131_1449730 

 

위의 테이블은 119 구급 대에서 위급한 일이 발생하는 목표지점까지의 지도를 표시한 것이다. 흰색으로 표시되어 있는 부분이 차가 지나갈 수 있는 길을 나타내고 회색으로 칠해져 있는 곳이 장애물을 의미한다. 이제 소방서에서 위급한 일이 발생한 목표지점까지 가장 빠른 시간에 도착할 수 있는 경로를 찾아보자. (출발점은 항상 왼쪽 맨 위(0,0)이고 도착점은 좌표로 주어진다. 119 구급차는 가로와 세로 방향으로만 움직일 수 있고 대각선으로는 움직일 수 없다.)


첫째 줄에 지도의 크기 M(1≤M≤100)×N(1≤N≤100)이 주어진다. 두 번째 줄에는 목표점 m,n이 주어진다. (단 M=m+1, N=n+1) 다음 N줄에는 M개의 값이 주어지며 각 값에서 1은 도로이고 0은 진입할 수 없는 물건이 놓여 있다.



첫째 줄에 최소 코너를 도는 횟수를 출력한다.


[Copy]
10 10
9 7
1 1 1 0 1 1 0 1 1 1
1 1 1 0 0 1 1 1 0 0
1 0 1 0 1 1 0 1 1 1
1 1 1 1 1 0 0 0 0 1
0 1 0 0 1 1 1 1 0 1
1 1 1 1 1 0 0 1 1 1
1 0 0 1 0 0 1 1 0 1
1 0 1 1 1 1 1 0 0 0
1 1 0 1 1 0 1 1 0 1
0 1 1 1 0 1 1 1 1 1
[Copy]
7





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.