5719 거의 최단 경로

www.acmicpc.net/problem/5719

5719번: 거의 최단 경로

1.접근

문제에서 요구하는 것은 원래의 최단경로를 제외한 길에서의 최단경로이다

따라서 다익스트라를 활용하여 최단경로를 구한 후 그 경로들을 제거해준후 다익스트라를 다시 돌리면 될것이다.

2.풀이

문제풀이 방법을 생각보다 간단하고 구현에서 시간이 걸린다.

접근에서 말한 것 처럼 다익스트라로 최단경로를 구해준다. 근데 여기서 중요한 것은 최단경로가 여러개 있을 수 있다는 것이다. 이것을 해결하는 방법에는 여러가지가 있겠지만 나는 도착지점부터 시작지점까지 올라가는 백트래킹을 활용했다.

다익스트라로 얻은 배열을 ans이라고 해보자. 가장 마지막 last 정점에 연결되는 정점들중 last정점의 ans[last]값과 ans[연결된정점]+간선(연결된정점->last)을 더해준게 같으면 그 경로는 최단거리에 포함되는 간선일 것이다. 최단거리에 포함되는 간선이라면 중복을 제거하는 set자료형에 넣고 그 정점에 도착하는 정점들로 계속 반복해서 실행해 준다.

마지막으로 set자료형에 들어와있는 값들을 하나씩 꺼내서 간선배열에서 없애준 후 다익스트라를 하면 된다.

한 정점을 향하는 모든 정점을 보기위해 where 배열을 선언하여 초기값 넣을 때 만들었고, 딕셔너리형으로 다익스트라를 구현해서 set자료형에 들어온 간선들을 없앨때의 시간을 줄였다.

자기 정점을 향하는 정점들을 볼 때 이미 방문한 곳에서 올수도 있으므로 ans[i]>ans[last]면 continue했다

시간초과를 한번 받았는데 중복되는 값들이 많이 들어올거라고 생각을 안하고 모두 재귀를 시켜서 시간초과였다.

if (i,last) not in delete: 를 활용해서 없을때만 들어가면 되게 바꿔주었다(set자료형이라 빠르게 가능하다).

 

3.코드

4.배운점

• 딕셔너리 형태로 다익스트라를 구현하는 연습이 잘 된것 같다.(del로 지우는 표현이 어색했음)

• 어떻게 풀어야할지는 알겠는데 구현이 까다로운것 같을때는 머리로만 생각해보는 것보다 그냥 한번 코딩해보는 것도 좋은것 같다