chogahui05   2년 전

정우를 위하여 중앙대학교에서 숭실대학교까지 가는 최소 비용과 거쳐야하는 거점의 수를 알아내는 프로그램을 작성하자.

최단 거리는 여러 개가 나올 수 있습니다. 실제 대회장에서는 스페셜 저지가 없기에..

최단 경로가 둘 이상이면서 거쳐야 하는 거점의 수가 서로 다른 경우에는 거쳐야 하는 거점의 수를 어떻게 출력해야 하나요?

라는 질문을 누군가 했었습니다.


그에 따른 답변은 거점의 수가 적은 답안으로 출력하시면 됩니다. 라고 되어 있습니다. 

이건 enenooo씨가 게시 글에서 물어보았었고요. 그런데 그러한 데이터가 없다는 글이 올라와 있습니다.

스페셜 저지가 없음에도 불구하고.


최단 경로가 여러개 있는 데이터가 밑에 있습니다. 그리고 문제에서는 양방향인지 단방향인지 설명이 없었지만.

단방향으로 풀면 맞았다는 이야기가 있어서, 그것을 기준으로 작성했고요.

인풋에 대한 설명을 해 보겠습니다.

거점의 수는 5개이고, 경로의 수는 5개입니다.

1에서 4까지 가는데 기본요금 3, 추가 요금 1, 걸리는 시간 1입니다.

4에서 2까지 가는데 기본요금 2, 추가 요금 1, 걸리는 시간 1입니다.

2에서 5까지 가는데 기본요금 3, 추가 요금 1, 걸리는 시간 1입니다.

1에서 3까지 가는데 기본요금 6, 추가 요금 1, 걸리는 시간 1입니다.

3에서 5까지 가는데 기본요금 2, 추가 요금 1, 걸리는 시간 1입니다.

그렇다면 그래프는

d8a39f01-e679-44fa-aa7e-21f3a7181b2a

이런 식이 될 겁니다. 걸리는 시간이 1이기 때문에, 추가 요금은 없고, 기본 요금만 있는 상태입니다. 

그렇기에 그래프가 이렇게 구축이 될 거고. 최단거리는 2개의 후보가 나올 수 있습니다.

보시다시피 위쪽으로 가는 것도 8이고, 아랫쪽으로 가는 것도 8입니다.

그러나, 더 적은 거점을 거쳐가는 것은 밑에 쪽이기에, 실제로는 8 4가 아닌 8 3이 출력되어야 합니다.

1->4->2->5로 가면 거치는 거점 수가 4이기 때문입니다.

답이 여러개가 나올 수 있다면, 스페셜 저지를 달아놓거나

아니라면 조건을 명확하게 해 주셔야 한다고 생각합니다. 만약에 의도했던 것이

스페셜 저지가 아니고, 최단 거리로 가는 후보가 여러 개가 있을 때, 더 적은 거점을 거쳐가는 답을 출력한다는 게 의도라면.

아래 데이터를 추가해 주세요.

startlink   1년 전

수정했습니다.

startlink   1년 전

재채점했습니다.

댓글을 작성하려면 로그인해야 합니다.