최소신장트리: 백준 9372 상근이의 여행

최소신장트리: 백준 9372 상근이의 여행

간단한 팁을 하나 남겨보고자 포스팅을 합니다. 제목에 쓰여있듯이 신장트리(spanning tree)라는 것에 대한 이야기예요.

문제와 풀이

---

문제 링크 : 백준 9372 - 상근이의 여행

👇펼쳐서 코드와 해설 읽기

문제를 보면 즉시 BFS로 풀어야겠다는 생각이 들죠.
최소신장트리에 대해서 모르는 상태였기 때문에 저도 그랬습니다.

신장 트리란 모든 정점을 포함하고 있는 그래프를 말합니다.
그리고 모든 정점을 가장 짧은 경로로 연결하는 그래프를 최소 신장 트리라고 합니다.
물론 몇가지 제약이 있지만 일단 개념은 그렇습니다(무향 그래프에서 가중치나 비용이 특별히 없을 때).
최소신장트리가 그려질 때에는 한 그래프에서 여러 형태로 존재할 수 있고, Self loop는 불가합니다.

최소신장트리에서 꼭 기억해야 할 점은 이것입니다. : 최소신장트리의 길이(간선의 수)는 (정점 - 1)개다.

그것을 알고 보면 이 문제는 BFS 문제가 아니라 트리 문제가 됩니다.🤗

public class Nick {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < t; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());
            for (int j = 0; j < m; j++) {
                br.readLine();
            }

            sb.append(n - 1).append(System.lineSeparator());
        }
        br.close();

        System.out.println(sb.toString());
    }

}

마무리

---

BFS로 풀고나서 다른 분들의 답안을 서칭하다가 최소신장트리 개념을 알게 되었는데요.
왜 이런 생각을 못하고 탐색을 했지?! 라는 생각이 절로 들었네요.
다시 비슷한 문제를 만나면 꼭 떠올릴 수 있어야겠죠..! 간단하지만 신기해서 꼭 소개하고 싶은 마음에 후딱 들고와 보았습니다!