• TOC {:toc}

이 글은 백준 온라인 저지의 1774번 문제를 풀이한 것을 모아놓은 글입니다.

일종의 연습 기록이며 제가 정답을 받은 코드와 참고할만한 다른 코드를 같이 기록합니다. 필요한 경우 코드에 대한 해설을 기록합니다만 코드는 통과했어도 해설은 틀릴 수 있기 때문에 가볍게 참고해주시길 부탁드립니다. 피드백은 편하신 방법으로 자유롭게 주시면 감사하겠습니다.

2021.07.09 (Python)

메모리 시간 코드 길이
101872 KB 1548 ms 1201 B
단계 시작 시각 끝난 시각 걸린 시간
문제 이해 11:30:36 11:33:05
풀이 생각 11:33:40 12:03:34
코딩 1-1 13:35:48 13:57:52
코딩 1-2 15:14:53 16:04:11
풀이 생각 2 + 코딩 2 20:17:07 21:05:08 
import sys
from math import sqrt, pow 
input = sys.stdin.readline

# 거리를 구하는 함수
def get_dist(a, b):
    x1, y1 = a
    x2, y2 = b
    return sqrt(pow(x1 - x2, 2) + pow(y1 - y2, 2))

# 루트 노드를 찾는 함수
def find(node):
    if parent[node] != node:
        parent[node] = find(parent[node])
    
    return parent[node]

# 두 노드를 연결하는 함수
def union(node_u, node_v):
    root_u = find(node_u)
    root_v = find(node_v)

    if rank[root_u] > rank[root_v]:
        parent[root_v] = root_u
    else:
        parent[root_u] = root_v

        if rank[root_u] == rank[root_v]:
            rank[root_v] += 1

N, M = map(int, input().split())

# 각 노드의 좌표를 담는 리스트
coord = [()] + [tuple(map(int, input().split())) for _ in range(N)]
# 해당 노드의 부모 노드를 저장하기 위한 리스트
parent = [i for i in range(N + 1)]
# 해당 노드의 랭크를 저장하기 위한 리스트
rank = [0 for _ in range(N + 1)]
# 간선 리스트
edges = []
res = 0

for _ in range(M):
    # 이미 연결된 두 노드를 받아서 
    A, B = map(int, input().split())
    # 연결한다.
    union(A, B)

# 각 노드를 순회하면서
for i in range(1, N + 1):
    for j in range(i + 1, N + 1):
        # 두 노드의 거리를 edges에 추가한다.
        edges.append((get_dist(coord[i], coord[j]), i, j))
# edges를 거리순으로 정렬한다.
edges.sort()

for edge in edges:
    dist, node_u, node_v = edge

    # 두 노드가 다른 루트 노드를 가지면
    if find(node_u) != find(node_v):
        # 연결한 뒤
        union(node_u, node_v)
        # 그 거리를 결과에 추가한다.
        res += dist

print(f"{res:.2f}")

아이디어 & 풀이

크루스칼 알고리즘을 이용했다.

  • 크루스칼 알고리즘은 [[wiki0:fc-algo-algorithm-20-kruskal]]{강의 정리글}을 참고한다.

우선 필요한 함수를 정의한다.

  • 두 좌표 사이의 거리를 구하는 get_dist 함수
  • 두 노드를 연결하는 union
  • 두 노드의 루트 노드를 찾으면서 경로의 모든 노드의 부모 노드를 루트 노드로 바꾸는 find 함수

이미 연결된 노드 상을 입력받으면서 union 함수로 연결한다.

  • 이미 연결된 노드 사이의 거리는 결과에 합치지 않기 때문에 연결만 하면 된다.

간선 리스트 edges를 만들어 정렬한다.

  • 모든 노드(1 ~ N)에 대해서 각 노드를 순회하면서 (거리, 출발 노드, 도착 노드)를 edges에 추가한다.
  • 간선에 방향이 있지 않기 때문에 i와 j를 연결할 때 둘 중 한 방향의 간선만 있어도 되므로 i는 1 ~ N - 1까지 j는 i + 1 ~ N까지 순회한다.

모든 노드 사이의 거리를 구하는 것이 너무 비효율적일 것 같아서 미리 연결되거나 연결하지 않아도 되는 간선은 제외하고 edges를 구성하고 싶었는데 마땅한 방법을 떠올리지 못했다.

거리가 최소인 간선부터 사이클이 생성되지 않도록 연결한다.

  • edges의 원소를 순회하면서 두 노드의 루트 노드가 일치하지 않으면 두 노드를 연결한 뒤 두 노드 사이의 거리를 res에 더한다.

피드백

2022.04.09 (JS)

메모리 시간 코드 길이
169512 KB 1888 ms 1514 B
단계 시작 시각 끝난 시각 걸린 시간
문제 이해 22:24:08 22:26:00
풀이 생각 22:40:07 22:59:24
코딩 22:59:25 23:59:23
디버깅 00:56:48 00:59:23 
const fs = require("fs");
const input = fs.readFileSync('/dev/stdin').toString().trim().split("\n");

function getDist(a, b) {
    const [x1, y1] = god[a];
    const [x2, y2] = god[b];

    return Math.sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2);
}

function find(n) {
    if (n !== parent[n]) {
        parent[n] = find(parent[n]);
    }
    return parent[n];
}

function union(n1, n2) {
    const r1 = find(n1);
    const r2 = find(n2);

    if (rank[r1] > rank[r2]) parent[r2] = r1;
    else {
        parent[r1] = r2;
        if (rank[r1] === rank[r2]) rank[r2] += 1;
    }
}

function kruskal() {
    lines.slice(N).forEach((nodes) => {
        const [a, b] = nodes.split(" ").map((n) => parseInt(n));
        if (find(a) !== find(b)) union(a, b);
    });

    let connected = 0;
    edges.forEach((edge) => {
        const [d, a, b] = edge;
        if (find(a) !== find(b)) {
            union(a, b);
            connected += d;
        }
    });

    return connected.toFixed(2);
}

const [NM, ...lines] = input;
const [N, M] = NM.split(" ").map((n) => parseInt(n));

const god = lines.slice(0, N).map((coord) => coord.split(" ").map((n) => parseInt(n)));
god.unshift([0, 0]);

// initialize
const parent = Array(N + 1)
    .fill()
    .map((elem, i) => i);
const rank = Array(N + 1).fill(0);

const edges = [];
for (let i = 1; i < N; i += 1) {
    for (let j = 2; j < N + 1; j += 1) {
        if (i === j) continue;
        edges.push([getDist(i, j), i, j]);
    }
}
edges.sort((a, b) => a[0] - b[0]);

console.log(kruskal());

디버그

  • getDist에서 소수점 2자리로 맞춰서 반환했더니 틀렸다. 길이는 그냥 구해진 값 그대로 반환하고 마지막 결과만 2자리로 맞춰서 출력했어야 헀다.

참고 답안

import sys
from heapq import heappop, heappush
from math import sqrt
input = sys.stdin.readline


def get_dist(a, b):
    x1, y1 = a
    x2, y2 = b
    return sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2)


def find(node):
    if parent[node] != node:
        parent[node] = find(parent[node])

    return parent[node]


def union(node_u, node_v):
    root_u = find(node_u)
    root_v = find(node_v)

    if rank[root_u] > rank[root_v]:
        parent[root_v] = root_u
    else:
        parent[root_u] = root_v

        if rank[root_u] == rank[root_v]:
            rank[root_v] += 1


N, M = map(int, input().split())

coord = [()] + [tuple(map(int, input().split())) for _ in range(N)]
parent = [i for i in range(N + 1)]
rank = [0 for _ in range(N + 1)]
edges = []
count = 0
res = 0

for _ in range(M):
    A, B = map(int, input().split())
    if find(A) != find(B):
        union(A, B)
        count += 1

for i in range(1, N + 1):
    for j in range(i + 1, N + 1):
        heappush(edges, (get_dist(coord[i], coord[j]), i, j))

while count != N - 1:
    dist, node_u, node_v = heappop(edges)

    if find(node_u) != find(node_v):
        union(node_u, node_v)
        res += dist
        count += 1

print(f"{res:.2f}")

아이디어 & 풀이

동일하게 크루스칼 알고리즘을 이용했지만, 간선 리스트를 필요한 만큼만 순회하기 때문에 실행이 훨씬 빠르다.

  • 최소 신장 트리는 모든 노드가 사이클 없이 연결되어 있기 때문에 간선의 수가 N - 1 개이다.
  • 노드를 연결할 때마다 count 값을 1씩 증가시켜 count 값이 N - 1이 될 때까지만 노드를 연결하면 연결을 끝난 이후의 간선 리스트를 순회하지 않아도 된다.
    • 연결된 간선의 수를 정확히 세야하기 때문에 이미 연결된 간선을 입력받아 연결할 때도 두 노드의 루트 노드가 같지 않은지 확인해야 한다.