문제풀이

해싱과 플로이드 와샬을 적절히 쓰면 쉽게 풀 수 있는 문제이다.

우선 노드가 string으로 들어오기 때문에 string을 int로 바꿔줄 필요가 있다.

이때 해싱을 사용한다. map을 이용해 지역의 이름을 숫자로 바꿔주면 배열에서 index 접근이 가능해지기 때문이다.

그다음은 내일로 티켓을 사는 경우와 그렇지 않은 경우에 대해 각각 최솟값을 구한다.

먼저 내일로 티켓을 사지 않는 경우는 그냥 플로이드 와살을 쓰면 된다.

내일로 티켓을 사는 경우는 교통수단이 무궁화, ITX라면 cost에 0을 넣어주고 STrain과 VTrain은 cost/=2.0;을 해준다.

그 후 경로에 따라 dist1,2배열로 최소비용을 구해주면 된다.

주의사항이 있다면 나도 이거 때문에 한번 틀렸다. STrain과 VTrain은 cost에 나누기 2를 해주기 때문에 double형을 사용해야 한다.

코드

• solution

문제링크

• boj/13168