문제 링크 :https://www.acmicpc.net/problem/13168
Map을 통한 문자열 활용과 플루이드 워샬을 적절히 섞은 문제라고 생각된다.
문제 접근은
- 모든 도시와 이동수단을 각각의 Map에 넣어준다.
- 출발도시부터 도착도시까지의 경로 도시들에 관한 value를 map으로부터 꺼내서 따로 배열에 저장한다.
- 플루이드 워샬 알고리즘을 활용하되, 한 번은 교통수단 별로 내일로 티켓이 적용된 비용을 적용한다.
- 배열에 저장한 출발-도착 정보에 따라 경로 비용을 더해준다.
1
처음에는 탈것의 종류가 무척 많아서 각각의 탈 것마다 출발 도시, 도착 도시의 정보를 저장하는 리스트를 만들어야한다고 생각했다.
문제를 읽다보니 내일로 티켓의 할인을 받지 못하는 이동 수단, 반틈만 받는 이동 수단, 전체 할인되는 이동 수단 총 3가지로 구분되는 것을 알 수 있었다.
따라서 이동 수단 역시 map에 키=이동수단, value=할인을 받는 그룹의 번호로 정리할 수 있었다.
2
플루이드 워샬을 내일로 티켓 적용, 미적용 2번 해야하기 때문에 이차원 배열을 2개 만들고 최대 값으로 설정한다.
자기 자신(2차원 배열의 대각선)은 항상 거리가 0이기 때문에 0으로 초기화해준다.
3
교통수단, 출발 도시, 도착 도시에 관한 정보를 입력받을 때 미리 내일로 티켓이 적용된 경우와 그렇지 않은 경우에 대한 전처리를 수행한다.
할인이 없는 경우에도 math.min을 사용한 이유는 동일한 출발, 도착 경로라도 교통수단만 다른 경우의 입력이 여러 개일 수 있다는 전제가 있기 때문이다.
4
전처리를 이전에 모두 수행했기 때문에 플루이드 워샬 코드는 비교적 짧다.
처음 코드를 짤 때 if문으로 i==k, i==j, k==j 등을 경우를 continue해주었다.
문제를 해결한 뒤 1페이지의 코드를 참조하였는데 if문 처리와 Math.min이 동일한 결과를 출력한다는 것을 알 수 있었다.
5
비용을 계산할 때 내일로 티켓을 끊은 경우, 티켓값을 더한 후 플루이드 워샬 처리가 된 이차원 배열에서 출발, 도착 도시 간의 비용을 꺼내어 더해준다.
문제 자체가 플루이드 워샬을 알면 쉽게 풀 수 있으니까 몇 가지 기믹으로 난이도를 올렸다는 생각이 들었다.
1.
동일한 출발, 도착 경로라도 교통수단만
다른 경우의 입력이 여러 개일 수 있다는 전제절반 할인을 받는 교통수단일 경우 홀수 비용일 때
소숫점 1자리까의 계산에 대한 요구를 명시하지 않음이 문제의 정답률이 낮은 이유가 이것때문이 아닐까 생각했다.
필자도 설마 소숫점 계산을 요구할까 싶었는데 결국 문제 해결이 안되서 질문 검색을 통해 요구사항을 알게 되었다.
개인적인 다른 문제로는 코드를 제대로 구현했는데도 통과가 안되어서 고민을 많이 했다.
문제는 Yes를 YES로, No를 NO로 출력해서였다...
PS. 항상 FASTIO가 빠른 것은 아닌 것 같다.
FASTIO :
BufferedReader :
