EDOC 2023-W 5회차 정모 (플로이드-워셜 / 최소 신장 트리)

A. 호석이 두 마리 치킨 (백준 21278번)

 

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

 

#python

from sys import stdin
import sys

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

for i in range(1, n+1):
    g[i][i] = 0

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

for i in range(1, n+1): # 경유지 i에 대해
    for j in range(1, n+1): # 출발 노드 j에 대해
        for k in range(1, n+1): # 도착 노드 k에 대해
            if g[j][i] + g[i][k] < g[j][k]:
                g[j][k] = g[j][i] + g[i][k]

ch1 = 1
ch2 = 1
acc = sys.maxsize

for i in range(1, n+1):
    for j in range(1, n-i+2):
        if j == i:
            continue
        tmp = 0
        for k in range(1, n+1):
            tmp += min(g[k][i], g[k][j])
        if tmp < acc:
            ch1 = i
            ch2 = j
            acc = tmp

print(ch1, ch2, acc * 2)

i는 1부터 n까지 반복하고 j는 1부터 n-i-+1까지 반복하게 했다. 그리고 작을 때만 (작거나 같을 때가 아니라) 업데이트하면 더 작은 건물 번호를 출력해야 된다는 조건에 만족한고 생각했다. 그런데 이렇게 제출했더니 19개의 데이터 중 14개만 맞았다. (오답)

 

#python

from sys import stdin
import sys

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

for i in range(1, n+1):
    g[i][i] = 0

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

for i in range(1, n+1): # 경유지 i에 대해
    for j in range(1, n+1): # 출발 노드 j에 대해
        for k in range(1, n+1): # 도착 노드 k에 대해
            if g[j][i] + g[i][k] < g[j][k]:
                g[j][k] = g[j][i] + g[i][k]

for i in range(1, n+1):
    for j in range(1, n+1):
        if j == i:
            continue
        tmp = 0
        for k in range(1, n+1):
            tmp += min(g[k][i], g[k][j])
        ans.append((tmp, i, j))

ans.sort()

print(ans[0][1], ans[0][2], ans[0][0] * 2)

그래서 그냥 단순무식하게 ans 배열에 (접근성, 건물1, 건물2) 순서의 튜플로 넣고 정렬 후 첫번째 값들을 출력하게 수정했다. 그랬더니 맞았다. (정답) 뭐가 다른건지 아직도 모르겠음...

 

+)

#python

from sys import stdin
import sys

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

for i in range(1, n+1):
    g[i][i] = 0

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

for i in range(1, n+1): # 경유지 i에 대해
    for j in range(1, n+1): # 출발 노드 j에 대해
        for k in range(1, n+1): # 도착 노드 k에 대해
            if g[j][i] + g[i][k] < g[j][k]:
                g[j][k] = g[j][i] + g[i][k]

ch1 = 1
ch2 = 1
acc = sys.maxsize

for i in range(1, n+1):
    for j in range(i+1, n+1):
        tmp = 0
        for k in range(1, n+1):
            tmp += min(g[k][i], g[k][j])
        if tmp < acc:
            ch1 = i
            ch2 = j
            acc = tmp

print(ch1, ch2, acc * 2)

진짜 바보인가... 그냥 반복문 범위가 이상한 것이었다........ (정답)

 

---

 

C. 전력난 (백준 6497번)

 

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

 

#python

from sys import stdin

def find(a):
    global parent
    if parent[a] == a:
        return a
    else:
        parent[a] = find(parent[a])
        return parent[a]

def union(a, b):
    a = find(a)
    b = find(b)
    if a != b:
        parent[b] = a
        return True
    else:
        return False

while True:
    m, n = map(int, stdin.readline().split())
    if m == 0 and n == 0:
        break
    
    sum = 0
    parent = [i for i in range(m+1)]
    edge = []

    for _ in range(n):
        a, b, c = map(int, stdin.readline().split())
        edge.append((a, b, c))
        sum += c

    edge.sort(key = lambda x : x[2])

    for x in edge:
        if union(x[0], x[1]):
            sum -= x[2]
    print(sum)

간단했던 MST 문제. (정답)