파이썬 알고리즘 315번 | [백준 20183번] 골목 대장 호석 - 효율성 2 (다익스트라 + 이분탐색)

315. 골목 대장 호석 - 효율성 2

1) 어떤 전략(알고리즘)으로 해결?

2) 코딩 설명

• 시작 점으로부터 도착점까지 가는동안 내야하는 "최대 요금의 최솟값"을 구해야 하는데 는 흔히 이분탐색에서 자주 나타나는 "최대의 최소화"꼴입니다.
• 따라서 "최대 상한 요금이 X원일 때, 시작점으로부터 도착점까지 C원내로 갈 수있는가?"라는 결정함수를 작성해 이분탐색을 진행합니다.
• 이 때, 최대 상한 요금이 되는 후보들(cand)들은 실제 통행요금
• 결정함수 내 도착점까지의 갈 수 있는지의 여부는 일반적인 다익스트라 알고리즘

<내 풀이>

<다른 분의 풀이 or 내 틀렸던 풀이, 문제점>

출처 : 출처

<반성 점>

• 다익스트라 개념 상실

def dijkstra(start): 
    minheapq=[]
    heapq.heappush(minheapq, (0,start)) 
		# w,v - 시작점으로부터 시작점 w : 0 / 시작점 노드부터 시작
    answer[start] = 0

    while minheapq: # 가장 w가 작은 노드부터 검사 (bfs 와 비슷 흐름)
        noww, nowv = heapq.heappop(minheapq)

        if answer[nowv] < noww :
						# nowv의 최단거리라고 기록돼있는 것이 noww 보다 작으면 더 이상 작아질 수 없다 
						# (왜냐면 이제부터는 noww+알파 로 최단경로 기록되니깐) 
            # nowv 보다 작다는 것은 이미 이 노드는 heappop 됐었다는 증거 
						# (처음에 heappop 될 수록 nowc가 가장 작은 상태)
            # => 이는 방문 완료, 이미 확정됐다는 증거
            # 한번 방문할 때 최단 경로가 이미 기록되어있다는 뜻이므로 방문 했을 시엔 검사할 필요 x
            continue

        for i in graph[nowv]: # 방문 안 한 노드라면 인접 노드 체크 필요
            cmpv, cmpw = i[0], i[1]  # 그래프에 (v,w) 로 담았었음 
            tmpcost = noww + cmpw # 현재 answer[cmpv] 에 기록된 최단경로와 비교해볼 대상
            if tmpcost < answer[cmpv]: # 현재 answer[cmpv] 에 기록된 최단경로보다 더 짧은 경로라면
                answer[cmpv] = tmpcost # answer[cmpv] 를 비교대상으로 대체
                heapq.heappush( minheapq, ( tmpcost, cmpv ) ) # 

• 이분 탐색 떠올리기

<배운 점>

1. 이분탐색

• 시작 점으로부터 도착점까지 가는동안 내야하는 "최대 요금의 최솟값"을 구해야 하는데 는 흔히 이분탐색에서 자주 나타나는 "최대의 최소화"꼴입니다.
• 따라서 "최대 상한 요금이 X원일 때, 시작점으로부터 도착점까지 C원내로 갈 수있는가?"라는 결정함수를 작성해 이분탐색을 진행합니다.
• 이 때, 최대 상한 요금이 되는 후보들(cand)들은 실제 통행요금
• 결정함수 내 도착점까지의 갈 수 있는지의 여부는 일반적인 다익스트라 알고리즘

2. 다익스트라, 플로이드 워셜 복습

• 다익스트라 개념 - 우선수위큐 (가중치 기준), BFS
• 플로이드와 다익스트라의 비교 - https://loosie.tistory.com/146
  • 
  • 다익스트라

    • 다익스트라 알고리즘은 우선순위 큐 + BFS의 형태를 가지고 있다.
    • 각 정점까지의 최단 거리를 저장하는 배열 dp[]를 유지하며, 정점을 방문할 때마다 인접한 정점을 모두 검사한다.
    • 간선 (u, v)를 검사한다고하면 u까지의 최단 거리에 (u, v)의 가중치를 더해 v까지의 경로의 길이를 찾는다.
    • 만약 이 길이가 최단거리라면 dp[v]를 갱신하고, (v, dp[v])를 큐에 넣는다.

  • 플로이드

    • 다익스트라나 벨만포드는 한 시작점에서 다른 모든 정점까지의 거리를 구해준다.
    • 모든 쌍 간의 최단 거리를 구하고 싶다면 플로이드 와샬 알고리즘을 사용하면 된다.