1800 인터넷 설치( 다익스트라 ,이분탐색)

https://www.acmicpc.net/problem/1800

1800번: 인터넷 설치

1.접근

간단한 문제인거같아 DFS로 목적지에 도달했을때 stack을 정렬해서 값을 찾아냈는데 시간초과를 받았다.(정렬을 너무 많이 사용하게 되서)

'x원으로 해결이 안되는데 x-1원으로 가능할까?' 라는 질문글에 있던 힌트를 보고 문제를 해결할 수 있었다.

 

2.풀이

이분탐색을 해가면서 다익스트라를 돌릴때마다 가능한 값이면 정답에 저장하도록 했다.

문제에서 남은선중 가장 비싼 하나의 값만 가지기로 했으므로 이분탐색으로 확인하는 값 이하인 길이는 가중치0, 확인하는 값 이상의 길이는 가중치1로 두고 다익스트라를 변형하여 풀어야한다.

1~N으로의 최단경로가 k 보다 커지면 불가능하고 도착할 수 있다면 정답으로 바꿔준다.

 

+헷갈렸던 부분)

이분탐색 가능 여부에 대해서 헷갈렸었다.

기준 잡은 값이 존재하지 않을 수 있는 거 아닌가? 라는 의문을 가졌지만 그건 최대값 구하는 문제일때 생기는 상황이였었다. 최소값을 구하는 것이므로 존재하는 값을 기준으로 나눠졌다.

 

3.코드

	# 설정한 수보다 크면 1
	from heapq import heappush, heappop
	import sys
	input = sys.stdin.readline
	INF = sys.maxsize
	def solution():
	global can
	def dijkstra(v, k):
	global can
	q = []
	ans = [INF] * (n + 1)
	ans[n]=0
	heappush(q, (0, n))
	while q:
	w, c = heappop(q)
	if w > k:
	break
	if c == 1:
	can = True
	break
	for where, weight in arr[c]:
	if w!=ans[c]:
	continue
	if weight > v:
	if ans[where]>ans[c]+1:
	ans[where]=ans[c]+1
	heappush(q,(ans[c]+ 1, where))
	else:
	if ans[where]>ans[c]:
	ans[where]=ans[c]
	heappush(q, (ans[c], where))
	answer = -1
	left = 0
	right = 1000000
	while left <= right:
	can = False
	mid = (left + right) // 2
	dijkstra(mid, k)
	if can:
	answer = mid
	right = mid - 1
	else:
	left = mid + 1
	print(answer)
	return
	if __name__ == '__main__':
	n, p, k = map(int, input().split())
	arr = [[] for _ in range(n + 1)]
	for i in range(p):
	a, b, w = map(int, input().split())
	arr[a].append((b, w))
	arr[b].append((a, w))
	solution()

view raw 인터넷설치.py hosted with ❤ by GitHub

4.배운점

• 다익스트라를 문제 상황에 맞게 변형해서 풀어나가는 것에 익숙해지자.
• 다익스트라의 시간복잡도 O(E * log E)를 다시 복습했다.(모든 간선을 확인 E + 모든 간선을 우선순위 큐에 넣음ElogE)