<div id="readability-page-1" class="page"><div><p data-ke-size="size16"><b>Question.</b></p>

<p data-ke-size="size16">최단경로 문제다. 코딩테스트에 정말 자주 나오는 문제이니 풀어보자.</p>
<figure data-origin-width="1104" data-origin-height="693" data-ke-mobilestyle="widthOrigin"><span data-url="https://blog.kakaocdn.net/dn/rC2XQ/btq7quVDyAc/NYyfMMSBOMcgTqdTkZ7pw1/img.png" data-lightbox="lightbox" data-alt=""><img src="https://blog.kakaocdn.net/dn/rC2XQ/btq7quVDyAc/NYyfMMSBOMcgTqdTkZ7pw1/img.png" data-origin-width="1104" data-origin-height="693" data-ke-mobilestyle="widthOrigin"></span></figure>


<hr contenteditable="false" data-ke-type="horizontalRule" data-ke-style="style1">
<p data-ke-size="size16"><b>Answer.</b></p>

<p data-ke-size="size16">최단경로 알고리즘 중에서도 '다익스트라 알고리즘' 문제다.</p>

<p data-ke-size="size16"><a href="https://sohyunwriter.tistory.com/39" target="_blank" rel="noopener">2021.01.16 - [Computer Science/Datastructure &amp; Algorithm] - 최단경로 알고리즘 (1) - 다익스트라 알고리즘</a></p>
<figure id="og_1623856557880" contenteditable="false" data-ke-type="opengraph" data-ke-align="alignCenter" data-og-type="article" data-og-title="최단경로 알고리즘 (1) - 다익스트라 알고리즘" data-og-description="*최단경로 알고리즘: 특정 지점까지 가장 빠르게 도달하는 방법을 찾는 알고리즘 *최단경로 알고리즘의 종류 1) 다익스트라 알고리즘 2) 플로이드 워셜 알고리즘 3) 벨만 포드 알고리즘 코딩테스" data-og-host="sohyunwriter.tistory.com" data-og-source-url="https://sohyunwriter.tistory.com/39" data-og-url="https://sohyunwriter.tistory.com/39" data-og-image="https://scrap.kakaocdn.net/dn/EgZGF/hyKAs5aGSH/y5KEfhrilkeq3b6n9QCgVK/img.png?width=460&amp;height=307&amp;face=0_0_460_307,https://scrap.kakaocdn.net/dn/e7QMe/hyKAlkFVga/3A6GSfM6S5W3MwADu4Bdr0/img.png?width=460&amp;height=307&amp;face=0_0_460_307,https://scrap.kakaocdn.net/dn/b0IZMv/hyKAeeMwxD/AQGDsKVKzkD6ErKZWTEyj0/img.png?width=460&amp;height=307&amp;face=0_0_460_307"><a href="https://sohyunwriter.tistory.com/39" target="_blank" rel="noopener" data-source-url="https://sohyunwriter.tistory.com/39">

<div>
<p data-ke-size="size16">최단경로 알고리즘 (1) - 다익스트라 알고리즘</p>
<p data-ke-size="size16">*최단경로 알고리즘: 특정 지점까지 가장 빠르게 도달하는 방법을 찾는 알고리즘 *최단경로 알고리즘의 종류 1) 다익스트라 알고리즘 2) 플로이드 워셜 알고리즘 3) 벨만 포드 알고리즘 코딩테스</p>
<p data-ke-size="size16">sohyunwriter.tistory.com</p>
</div>
</a><img src="https://scrap.kakaocdn.net/dn/EgZGF/hyKAs5aGSH/y5KEfhrilkeq3b6n9QCgVK/img.png?width=460&amp;height=307&amp;face=0_0_460_307,https://scrap.kakaocdn.net/dn/e7QMe/hyKAlkFVga/3A6GSfM6S5W3MwADu4Bdr0/img.png?width=460&amp;height=307&amp;face=0_0_460_307,https://scrap.kakaocdn.net/dn/b0IZMv/hyKAeeMwxD/AQGDsKVKzkD6ErKZWTEyj0/img.png?width=460&amp;height=307&amp;face=0_0_460_307"></figure>

<p data-ke-size="size16">다익스트라 알고리즘은 매우 많이 나와서 아예 함수로 아래와 같이 snippet으로 만들어뒀다.</p>

<pre id="code_1623856328438" data-ke-language="python" data-ke-type="codeblock"><code>import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)

def dijkstra(graph, pos, distance, visited, n):
    q = []

    heapq.heappush(q, (0, pos))
    distance[pos] = 0

    while q:
        dist, now = heapq.heappop(q)
        if distance[now] &lt; dist:
            continue
        for i in graph[now]:
            cost = distance[now] + i[1]
            if cost &lt; distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))

    return distance

def solve(n, m, pos, edges):
    graph = [[] for i in range(n + 1)]
    visited = [False] * (n + 1)
    distance = [INF] * (n + 1)

    for start, dest, cost in edges:
        graph[start].append((dest, cost))

    dijkstra(graph, pos, distance, visited, n)

    return distance

if __name__ == "__main__":
    n, m = map(int, input().split())
    pos = int(input())
    edges = [list(map(int, input().split())) for _ in range(m)]

    distance = solve(n, m, pos, edges)

    for i in range(1, n+1):
        if distance[i] == INF:
            print("INF")
        else:
            print(distance[i])</code></pre>

<table data-ke-align="alignLeft">
<tbody>
<tr>
<td colspan="2">sol 1)&nbsp;</td>
</tr>
<tr>
<td>Time Complexity</td>
<td>O(ElogV)</td>
</tr>
<tr>
<td>Space Complexity</td>
<td>O(V^2)</td>
</tr>
</tbody>
</table>
<p data-ke-size="size16">**입력까지 고려했을 때는 그래프를 adjacency matrix로 만들었기 때문에 O(V^2)이나,&nbsp;</p>
<p data-ke-size="size16">다익스트라 알고리즘 자체의 space complexity는 O(V+E)</p>

<p data-ke-size="size16">(참고) <a href="https://stackoverflow.com/questions/32608288/time-space-complexity-of-adjacency-matrix-and-adjacency-list" target="_blank" rel="noopener">https://stackoverflow.com/questions/32608288/time-space-complexity-of-adjacency-matrix-and-adjacency-list</a></p>
<figure id="og_1623856883427" contenteditable="false" data-ke-type="opengraph" data-ke-align="alignCenter" data-og-type="website" data-og-title="Time/Space complexity of adjacency matrix and adjacency list" data-og-description="I am reading &quot;Algorithms Design&quot; By Eva Tardos and in chapter 3 it is mentioned that adjacency matrix has the complexity of O(n^2) while adjacency list has O(m+n) where m is the total number of edg..." data-og-host="stackoverflow.com" data-og-source-url="https://stackoverflow.com/questions/32608288/time-space-complexity-of-adjacency-matrix-and-adjacency-list" data-og-url="https://stackoverflow.com/questions/32608288/time-space-complexity-of-adjacency-matrix-and-adjacency-list" data-og-image="https://scrap.kakaocdn.net/dn/cp1UOW/hyKApm41Dl/Lkl5zkv7PqQhAOQaysmUCK/img.png?width=316&amp;height=316&amp;face=0_0_316_316"><a href="https://stackoverflow.com/questions/32608288/time-space-complexity-of-adjacency-matrix-and-adjacency-list" target="_blank" rel="noopener" data-source-url="https://stackoverflow.com/questions/32608288/time-space-complexity-of-adjacency-matrix-and-adjacency-list">

<div>
<p data-ke-size="size16">Time/Space complexity of adjacency matrix and adjacency list</p>
<p data-ke-size="size16">I am reading "Algorithms Design" By Eva Tardos and in chapter 3 it is mentioned that adjacency matrix has the complexity of O(n^2) while adjacency list has O(m+n) where m is the total number of edg...</p>
<p data-ke-size="size16">stackoverflow.com</p>
</div>
</a><img src="https://scrap.kakaocdn.net/dn/cp1UOW/hyKApm41Dl/Lkl5zkv7PqQhAOQaysmUCK/img.png?width=316&amp;height=316&amp;face=0_0_316_316"></figure>
            
</div></div>

sohyunwriter

Question.
 
최단경로 문제다. 코딩테스트에 정말 자주 나오는 문제이니 풀어보자.
 
 
Answer.
 
최단경로 알고리즘 중에서도 '다익스트라 알고리즘' 문제다.
 
2021.01.16 - [Computer Science/Datastructure & Algorithm] - 최단경로 알고리즘 (1) - 다익스트라 알고리즘
 
다익스트라 알고리즘은 매우 많이 나와서 아예 함수로 아래와 같이 snippet으로 만들어뒀다.
 
import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)
def dijkstra(graph, pos, distance, visited, n):
    q = []
    heapq.heappush(q, (0, pos))
    distance[pos] = 0
    while q:
        dist, now = heapq.heappop(q)
        if distance[now] < dist:
            continue
        for i in graph[now]:
            cost = distance[now] + i[1]
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))
    return distance
def solve(n, m, pos, edges):
    graph = [[] for i in range(n + 1)]
    visited = [False] * (n + 1)
    distance = [INF] * (n + 1)
    for start, dest, cost in edges:
        graph[start].append((dest, cost))
    dijkstra(graph, pos, distance, visited, n)
    return distance
if __name__ == "__main__":
    n, m = map(int, input().split())
    pos = int(input())
    edges = [list(map(int, input().split())) for _ in range(m)]
    distance = solve(n, m, pos, edges)
    for i in range(1, n+1):
        if distance[i] == INF:
            print("INF")
        else:
            print(distance[i])
 
sol 1) 
Time Complexity
O(ElogV)
Space Complexity
O(V^2)
**입력까지 고려했을 때는 그래프를 adjacency matrix로 만들었기 때문에 O(V^2)이나, 
다익스트라 알고리즘 자체의 space complexity는 O(V+E)
 
(참고) https://stackoverflow.com/questions/32608288/time-space-complexity-of-adjacency-matrix-and-adjacency-list

백준 1753. 최단경로 (+파이썬 풀이)

댓글