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.코드

	import sys
	from heapq import *
	sys.setrecursionlimit(10**9)
	INF=sys.maxsize
	input=sys.stdin.readline
	def dijkstra(s):
	ans=[INF]*n
	ans[s]=0
	Q=[]
	heappush(Q,(0,s))
	while Q:
	a,b=heappop(Q)
	if ans[b]<a:
	continue
	else:
	for q in adj[b]:
	w=adj[b][q]
	if ans[q]>ans[b]+w:
	ans[q]=ans[b]+w
	heappush(Q,(ans[q],q))
	return ans
	def tracking(ans,last):
	global delete
	temp=ans[last]
	for i in where[last]:
	if ans[i]>ans[last]:
	continue
	elif ans[i]+adj[i][last]==temp:
	if (i,last) not in delete:
	delete.add((i,last))
	tracking(ans,i)
	while 1:
	n,m=map(int,input().split())
	if n==0 and m==0:
	break
	s,d=map(int,input().split())
	adj=[{}for _ in range(n)]
	where=[[]for _ in range(n)]
	delete=set()
	for i in range(m):
	a,b,c=map(int,input().split())
	adj[a][b]=c
	where[b].append(a)
	ans=dijkstra((s))
	tracking(ans,d)
	for a,b in delete:
	del adj[a][b]
	temp=dijkstra(s)[d]
	if temp==INF:
	print(-1)
	else:
	print(temp)

view raw 거의 최단경로.py hosted with ❤ by GitHub

4.배운점

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

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