수다닷컴

질문 제목 : 좌우회전, 유턴이 포함된 최단경로 찾기일반 최단 경로 찾기라면 할 수 있을 것 같은데 좌우회전 금지, 유턴 가능 지역을 포함한 최단 경로 찾기라 어떻게 해야 될지 모르겠네요. 문제 설명은 잘 되어 있는거 같은데 도무지 해결을 못하겠습니다. 설명 좀 부탁 드려도 될까요?질문 내용 :
교통 문제는 날로 심각해지고 있다. 이에 어느 택시회사에서는 고객의 서비스 향상을 위하여 차량항법 시스템을 개발하려고 한다. 이를 위하여 아래와 같이 최적 경로를 찾는 프로그램을 개발하려고 한다.
어느 도시의 지도가 n×n의 바둑판 모양으로 되어있다. 단, 3 ≤ n ≤ 9. 아래의 예제는 4×4로 된 지도이다.
지도에서 각각의 교차점 이름을 좌에서 우로, 위에서부터 아래로 다음과 같이 명명하기
로 한다.
00, 01, ... 0(n-1), / 10, 11, ... 1(n-1), / ... , / (n-1)0, (n-1)1, ... (n-1)(n-1)

교차점에 따라 좌회전 또는 우회전 금지도 있을 수 있다. 또한 교차점에 따라 u-턴(turn)도 가능하다. 그러나 직진 금지는 없다고 가정하며, 모든 도로는 양방향 통행이 가능하다. 또한 두 교차점 사이의 도로에는 자동차가 통과하는데 걸리는 시간이 주어지며, 각 도로는 진행 방향에 무관하게 같은 시간이 소요된다. 이러한 지도가 주어질 때 한 교차점(출발점)에서 다른 교차점(도착점)까지의 최단 시간이 소요되는 경로를 찾기 위한 프로그램을 작성하시오.

[입력]
프로그램의 입력 형식은 아래 예제의 입력을 참조한다. 각각의 좌회전 또는 우회전 금지에 대한 입력은 세 개의 교차점 이름으로 한 줄에 주어진다. 이는 자동차가 첫 번째 교차점에서 두 번째 교차점을 지나서 세 번째 교차점 방향으로의 회전이 불가능함을 의미한다. 또한 u-턴의 경우는 두 개의 교차점 이름이 한 줄에 입력되며, 이는 자동차가 첫 번째 교차점에서 두 번째 교차점 방향으로 진행하여 두 번째 교차점에서 다시 첫 번째 교차점 방향으로 갈 수 있음을 의미한다.
지도에 어떠한 제한조건들이 주어지더라도 한 교차점에서 다른 교차점으로 반드시 도달 가능하다고 가정하며, 이러한 제한조건들과 u-턴 등에 관한 입력의 수는 모두 합해서 최대 60으로 한정한다. 또한 각 도로의 주행시간은 1에서 20까지의 정수이다.
[출력]
첫 줄에 최단 경로 상에 있는 교차점 이름을 시작점부터 도착점까지 차례로 출력하고, 다음 줄에는 그 경로에 소요되는 시간을 출력한다.
[예제] 위의 그림에 대한 입력과 출력은 다음과 같다.
입력 :
4 ------- n = 4
00 33 ------- 출발점(00)과 도착점(33)
5 4 15 ------- 각 도로의 주행시간
6 2 3 6 좌에서 우로
9 2 3 위에서 아래로
18 19 17 4 차례로
16 5 3 입력된다.
15 7 2 20
9 2 10
5 ------- 좌/우회전 금지 조건의 개수
00 01 11 ------ 좌/우회전에 대한
02 12 13 제한조건들
12 22 23
22 32 33
22 23 33
4 ------- u-턴 가능한 교차점의 개수
02 01 ------- u-턴 가능한 교차점들
12 11
22 21
32 31
출력 :
00 01 02 12 11 12 13 23 22 32 31 32 33
42

신청하기