[백준 1753, 11404, 13549 ] - Python

• 취알스 6주차 최단거리 - 3/4

1753 최단경로
다익스트라 알고리즘을 이용하였다. 사실 이코테 강의에 나온 코드랑 같음.

import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)

n, m = map(int, input().split())
start = int(input())

graph = [[]for i in range(n+1)]
distance = [INF] *(n+1)

for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))

def dijkstra(start):
    q=[]
    heapq.heappush(q, (0, start)) # (최단거리, 노드)
    distance[start]=0
    while q:
        dist, now = heapq.heappop(q)
        if distance[now] < dist:
            continue
        for i in graph[now]:
            cost = dist + i[1]
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))

dijkstra(start)
for i in range(1, n+1):
    if distance[i] == INF:
        print("INF")
    else:
        print(distance[i])

11404 플로이드
모든 노드에 대해 다익스트라를 수행해줘야한다는 점을 제외하고 위와 거의 같음.

import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)

n = int(input())
m = int(input())
graph = [[] for i in range(n+1)]

for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))

def dijkstra(start):   
    distance = [INF] *(n+1)
    q=[]
    heapq.heappush(q, (0, start)) #(최단거리, 노드)
    distance[start]=0
    while q:
        dist, now = heapq.heappop(q)
        if distance[now] < dist:
            continue
        for i in graph[now]:
            cost = dist + i[1]
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))
    for i in range(1, n+1):
        if distance[i]==INF:
            print(0, end=' ')
        else: 
            print(distance[i], end=' ')
        
for i in range(1, n+1):
    dijkstra(i)
    print()

13549 숨바꼭질3
기본적으로 bfs를 이용한다.

import sys
from collections import deque

n, k = map(int, sys.stdin.readline().split())
dist = [0]*100001
# 거리를 담은 배열을 10만까지만 잡아주었다.
# 목적지가 어디라고 하더라도 그 2배를 먼저 하는 것보다는 -1을 먼저 해서 5만 이하로 내린 다음 2배를 하는 것이 이득이기 때문인데,
# 왜 그런지는 좀 더 생각해봐야겠다.

def bfs(s):
    queue = deque()
    queue.append(s)
    while queue:
        x = queue.popleft()
        if x==k:
            return dist[x]
        for nx in (x-1, x+1, 2*x):
            if 0 <= nx <= 100000 and not dist[nx]:
                if nx == 2*x and x != 0:
                    dist[nx] = dist[x]
                    queue.appendleft(nx) 
                    # 우선순위 큐 대신,
                    # 2*X로 순간이동하는게 시간이 덜 들어서 우선순위가 높으므로 큐에서 먼저 popleft되도록 왼쪽에 삽입함. 이것이 0-1 bfs라고 함.
                else:
                    dist[nx] = dist[x]+1
                    queue.append(nx)

print(bfs(n))