[BOJ/9372/Golang] 백준 9372 - 상근이의 여행

여담

MST (Minimum Spanning Tree, 최소 신장 트리) 공부 중에 MST 문제로 이 문제가 포함되어 있는 것을 보고 풀게 되었습니다.

접근 방식

처음에는 "어 그냥 노드 개수 - 1 아닌가?" 하고 "에이 설마.." 했습니다. 그러곤 MST를 공부하면서 익힌 Kruskal 알고리즘을 적용해서 풀어보고자 했습니다. 그러나 제출한 코드에 오류가 있는지 WA를 받아서 질문을 검색하다가 N-1이 답이라는 사실을 알게 되었습니다...

용어 정리

일반적인 그래프에서 사이클을 제거한 후에 Tree로 만들면, 이를 Spanning Tree라 합니다.

또한 Tree의 특성 상, 간선(edge)의 수는 정점(vertex)의 수가 N 개 일 때, N-1개가 됩니다.

이러한 상황에서 MST는 Spanning Tree 들 중, 간선(edge)의 가중치 합이 최소가 되는 Spanning Tree를 의미합니다.

N-1이 이 문제의 정답인 이유

이 문제는 특수하게도 모든 간선(edge)의 가중치가 1입니다. 모든 간선(edge)의 가중치가 1인 그래프의 Spanning Tree를 모두 그려보면, 모든 Spanning Tree가 곧 MST가 됨을 알 수 있고, 그 Tree의 가중치는 정점(vertex)의 개수 N에서 1을 뺀 N-1이 됩니다.

이 내용은 좀 더 이해하게 되면 추가 서술해보겠습니다.

코드

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
)

var (
    w  = bufio.NewWriter(os.Stdout)
    sc = bufio.NewScanner(os.Stdin)
)

func init() {
    sc.Split(bufio.ScanWords)
}

func main() {
    defer w.Flush()
    T := scanInt()
    for ; T > 0; T-- {
        nums := scanInts(2)
        N, M := nums[0], nums[1]
        for i := 0; i < M; i++ {
            nums = scanInts(2)
        }
        fmt.Fprintln(w, N-1)
    }
}

func scanInt() int {
    sc.Scan()
    n, _ := strconv.Atoi(sc.Text())
    return n
}

func scanInts(n int) []int {
    res := make([]int, n)
    for i := range res {
        res[i] = scanInt()
    }
    return res
}

마무리

여기까지 따라오시느라 고생 많으셨습니다. 만약 이 글이 도움이 되셨다면 글 좌측 하단의 하트❤를 눌러주시면 감사하겠습니다.

혹시라도 글에 이상이 있거나, 이해가 가지 않으시는 부분, 또는 추가적으로 궁금하신 내용이 있다면 주저 마시고 댓글💬을 남겨주세요! 빠른 시간 안에 답변을 드리겠습니다 😊