EDOC 2023-W 3회차 과제 (다익스트라 / 벨만-포드)

08-4. 다익스트라

 

056. 최단경로 (백준 1753번)

 

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

 

from sys import stdin
from queue import PriorityQueue
import sys

v, e = map(int, stdin.readline().split())
g = [[] for _ in range(v+1)]
dst = [sys.maxsize] * (v+1)
visited = [False] * (v+1)
que = PriorityQueue()

start = int(stdin.readline())
dst[start] = 0
que.put((0, start))

for _ in range(e):
    a, b, c = map(int, stdin.readline().split())
    g[a].append((b, c))

while que.qsize() > 0:
    now = que.get()
    if visited[now[1]]:
        continue
    visited[now[1]] = True
    for next in g[now[1]]:
        if dst[now[1]] + next[1] < dst[next[0]]:
            dst[next[0]] = dst[now[1]] + next[1]
            que.put((dst[next[0]], next[0]))

for i in range(1, v+1):
    if visited[i]:
        print(dst[i])
    else:
        print("INF")

처음에는 dst 값들을 11로 초기화를 해주었다. (오답) 가중치의 최댓값이 10이기 때문에 11로 초기화하면 된다고 생각했는데, 생각해보니 경로의 거리는 당연히 10보다 길어질 수 있기 때문에 sys.maxsize로 초기화해줘야 하는 것이었다. 바보... (정답) 그리고 처음 알게 된 건! 우선순위 큐는 while que: 라고 쓰면 안 되고 while que.qsize(): 라고 써야 한다. 이유는 모르겠으나 그냥 큐 이용하는 것처럼 전자로 하니까 무한루프를 도는 것 같았다. 추가로, 왜 업데이트한 노드들만 우선순위 큐에 넣어야 하나 했는데, 유추하건대 모든 노드를 넣어도 되긴 하지만 비효율적이어서 그런 것 같다. 모든 노드를 다 넣으면 우선순위 큐에 무한값이랑 필요없는 값들이 많이 남아있게 되어 불필요한 반복이 일어날 것 같다. 실제로 제출해보니 시간 초과는 안 떴지만 시간이 2배로 차이가 났다. 

 

---

 

057. 최소비용 구하기 (백준 1916번)

 

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

 

from sys import stdin
import sys
from queue import PriorityQueue

n = int(stdin.readline())
m = int(stdin.readline())
g = [[] for _ in range(n+1)]
dst = [sys.maxsize] * (n+1)
visited = [False] * (n+1)
que = PriorityQueue()

for _ in range(m):
    s, e, w = map(int, stdin.readline().split())
    g[s].append((e, w))

start, end = map(int, stdin.readline().split())
dst[start] = 0
que.put((0, start))

while que.qsize() > 0:
    now = que.get()
    if visited[now[1]]:
        continue
    visited[now[1]] = True
    for next in g[now[1]]:
        if dst[now[1]] + next[1] < dst[next[0]]:
            dst[next[0]] = dst[now[1]] + next[1]
            que.put((dst[next[0]], next[0]))

print(dst[end])

56번 문제와 매우 비슷한 문제. (정답)

 

---

 

058. K번째 최단경로 찾기 (백준 1854번)

 

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

 

from sys import stdin
import sys
import heapq

n, m, k = map(int, stdin.readline().split())
g = [[] for _ in range(n+1)]
dst = [[sys.maxsize] * k for _ in range(n+1)]

for _ in range(m):
    s, e, w = map(int, stdin.readline().split())
    g[s].append((e, w))

que = [(0, 1)]
dst[1][0] = 0

while que:
    cost, node = heapq.heappop(que)
    for nnode, ncost in g[node]:
        c = cost + ncost
        if dst[nnode][k-1] > c: # 아직 k번째 최단경로를 못 찾았다면
            dst[nnode][k-1] = c
            dst[nnode].sort()
            heapq.heappush(que, (c, nnode))

for i in range(1, n+1):
    if dst[i][k-1] == sys.maxsize:
        print(-1)
    else:
        print(dst[i][k-1])

처음에는 문제 분석하기, 손으로 풀어 보기까지만 보고 풀어보고자 했으나 너무 어려워서 결국 코드까지 다 보고 그냥 거의 따라 쓴 수준으로 풀었다... 특정 도시까지 갈 수 있는 경로의 길이가 여러개이므로 거리 배열이 이차원 배열이어야 한다는 점과 방문한 노드를 또 방문해도 되기 때문에 visited 배열을 없애야 한다는 점이 이 문제의 포인트인 것 같다. 그리고 그래프에는 (노드, 가중치) 순서로 데이터를 넣는데 힙큐에는 (가중치, 노드) 순서로 데이터를 넣는다는 것도 주의할 점이다! 추가로 이 문제를 풀면서 heapq를 학습할 수 있었다.  (정답)

 

---

08-5. 벨만-포드

 

059. 타임머신 (백준 11657번)

 

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

 

from sys import stdin
import sys

n, m = map(int, stdin.readline().split())
e = []
dst = [sys.maxsize] * (n+1)
check = False

for _ in range(m):
    a, b, c = map(int, stdin.readline().split())
    e.append((a, b, c))

dst[1] = 0

for _ in range(n-1):
    for a, b, c in e:
        if dst[a] != sys.maxsize and dst[a] + c < dst[b]:
            dst[b] = dst[a] + c

for _ in range(n-1):
    for a, b, c in e:
        if dst[a] != sys.maxsize and dst[a] + c < dst[b]:
            check = True
            break

if not check:
    for i in range(2, n+1):
        if dst[i] == sys.maxsize:
            print(-1)
        else:
            print(dst[i])
else:
    print(-1)

벨만-포드 알고리즘의 특징은 인접행렬 또는 인접리스트를 쓰는 것이 아닌, 에지들이 그대로 담긴 에지 배열을 쓴다는 것이다. 처음 접하는 알고리즘이라 처음에는 와닿지 않고 어려워보였으나 이해하고 나니 그닥 복잡하지 않았다. (정답)

 

---

 

060. 오민식의 고민 (백준 1219번)

 

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

 

from sys import stdin
import sys

n, start, end, m = map(int, stdin.readline().split())
e = []
dst = [sys.maxsize] * n
check = False

for _ in range(m):
    a, b, c = map(int, stdin.readline().split())
    e.append((a, b, c)) # 도시로 갈 때 교통수단 비용

city = list(map(int, stdin.readline().split())) # 도시에서 벌 수 있는 비용
for i in range(m):
    tmp = list(e[i])
    tmp[2] -= city[tmp[1]]
    e[i] = tuple(tmp)

dst[start] = city[start] * (-1)

for _ in range(n-1):
    for a, b, c in e:
        if dst[a] != sys.maxsize and dst[a] + c < dst[b]:
            dst[b] = dst[a] + c

for _ in range(n+101):
    for a, b, c in e:
        if dst[a] != sys.maxsize and dst[a] + c < dst[b]:
            dst[b] = dst[a] + c
            if b == end:
                check = True
                break

if not check:
    if dst[end] == sys.maxsize:
        print("gg")
    else:
        print(dst[end] * (-1))
else:
    print("Gee")

교재에서는 에지 업데이트를 n-1번이 아닌 충분히 큰 수(100)만큼 추가로 돌리면서 업데이트를 하도록 했다. 나는 문제 분석하기만 읽고 풀었더니 교재와는 조금 다르게 풀었다. 우선 구해야 하는 것이 최단 경로가 아니라 최대 비용이므로 가중치들을 전부 부호를 바꿔서 넣고 최단 경로를 구한 후 마지막에 다시 부호를 뒤집어 주었다. 그리고 도시까지 가는데에 필요한 비용과 그 도시에서 벌 수 있는 비용을 합쳐서 dst 배열에 넣어두었다. 그런데 17%틀... (오답) 게시판을 뒤져보니 반례는 다음과 같았다. 

3 0 2 4
0 1 9999
1 2 9999
1 1 9999
0 2 0
10000 10000 10000

벌 수 있는 돈이 1씩 조금씩 늘어나는데 실제로 사이클은 몇천번을 돌 수는 없으니 2000으로 출력되는 것 같다. 

 

from sys import stdin
import sys

n, start, end, m = map(int, stdin.readline().split())
e = []
dst = [sys.maxsize] * n
check = False

for _ in range(m):
    a, b, c = map(int, stdin.readline().split())
    e.append((a, b, c)) # 도시로 갈 때 교통수단 비용

city = list(map(int, stdin.readline().split())) # 도시에서 벌 수 있는 비용
for i in range(m):
    tmp = list(e[i])
    tmp[2] -= city[tmp[1]]
    e[i] = tuple(tmp)

dst[start] = city[start] * (-1)

for _ in range(n-1):
    for a, b, c in e:
        if dst[a] != sys.maxsize and dst[a] + c < dst[b]:
            dst[b] = dst[a] + c

for _ in range(n-1):
    for a, b, c in e:
        if dst[a] != sys.maxsize and dst[a] + c < dst[b]: # 수정한 부분
            dst[b] = sys.maxsize * (-1) # 수정한 부분
            if b == end:
                check = True
                break

if not check:
    if dst[end] == sys.maxsize:
        print("gg")
    else:
        print(dst[end] * (-1))
else:
    print("Gee")

그래서 dst[b] = sys.maxsize * (-1) 이 부분을 고쳐주었다. 사이클을 무한번 돈 효과를 내기 위함이다. 그런데도 49%틀... (오답) 다시 게시판이랑 구글을 눈물나게 뒤졌다. 그래서 찾게 된 반례!!

1 0 0 2
0 0 0
0 0 7
6

바로 n이 1일 때이다... n이 1이면 사이클을 판단하는 두번째 반복문이 아예 돌지 않는다는 것을 알게 되었다.

 

from sys import stdin
import sys

n, start, end, m = map(int, stdin.readline().split())
e = []
dst = [sys.maxsize] * n
check = False

for _ in range(m):
    a, b, c = map(int, stdin.readline().split())
    e.append((a, b, c)) # 도시로 갈 때 교통수단 비용

city = list(map(int, stdin.readline().split())) # 도시에서 벌 수 있는 비용
for i in range(m):
    tmp = list(e[i])
    tmp[2] -= city[tmp[1]]
    e[i] = tuple(tmp)

dst[start] = city[start] * (-1)

for _ in range(n-1):
    for a, b, c in e:
        if dst[a] != sys.maxsize and dst[a] + c < dst[b]:
            dst[b] = dst[a] + c

for _ in range(n):
    for a, b, c in e:
        if dst[a] != sys.maxsize and dst[a] + c < dst[b]:
            dst[b] = sys.maxsize * (-1)
            if b == end:
                check = True
                break

if not check:
    if dst[end] == sys.maxsize:
        print("gg")
    else:
        print(dst[end] * (-1))
else:
    print("Gee")

그래서 n이 1이더라도 반복문을 한번이라도 돌도록 for _ in range(n): 로 고쳐주었다. 그랬더니 드디어 정답. ㅠㅠ (정답) 플래 문제를 내 손으로 풀다니... 물론 구글링과 게시판 참고는 했지만 책의 코드를 그대로 쓰지 않았다는 점에서 너무 뿌듯했다. ㅎㅎ