백준 - 9372번(상근이의 여행)

문제 출처: https://www.acmicpc.net/problem/9372

문제

• 상근이는 겨울방학을 맞아 N개국을 여행하면서 자아를 찾기로 마음먹었다.

• 하지만 상근이는 새로운 비행기를 무서워하기 때문에, 최대한 적은 종류의 비행기를 타고 국가들을 이동하려고 한다.

• 이번 방학 동안의 비행 스케줄이 주어졌을 때, 상근이가 가장 적은 종류의 비행기를 타고 모든 국가들을 여행할 수 있도록 도와주자.

• 상근이가 한 국가에서 다른 국가로 이동할 때 다른 국가를 거쳐 가도(심지어 이미 방문한 국가라도) 된다.

• BFS 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    private static class Node {

        int vertex;
        Node next;

        public Node(int vertex, Node next) {
            this.vertex = vertex;
            this.next = next;
        }

    }

    public static void main(String[] args) throws IOException {
        StringBuilder sb = new StringBuilder();
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        int T = Integer.parseInt(reader.readLine()); // 테스트케이스 개수

        while (T-- > 0) {
            StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
            int N = Integer.parseInt(tokenizer.nextToken()); // 국가의 수
            int M = Integer.parseInt(tokenizer.nextToken()); // 비행기의 종류

            Node[] adjList = new Node[N + 1]; // 인접 리스트. 1-based index

            int from = 0;

            for (int i = 0; i < M; i++) {
                tokenizer = new StringTokenizer(reader.readLine());
                from = Integer.parseInt(tokenizer.nextToken());
                int to = Integer.parseInt(tokenizer.nextToken());

                adjList[from] = new Node(to, adjList[from]);
                adjList[to] = new Node(from, adjList[to]);
            }

            sb.append(bfs(adjList, from)).append("\n");
        }

        System.out.println(sb);
    }

    private static int bfs(Node[] adjList, int start) {
        Queue<Integer> queue = new ArrayDeque<>();
        queue.offer(start);

        boolean[] visited = new boolean[adjList.length];

        int result = -1;

        while (!queue.isEmpty()) {
            int target = queue.poll();

            if (visited[target]) continue;

            visited[target] = true;
            result++;

            for (Node node = adjList[target]; node != null; node = node.next) {
                if (!visited[node.vertex]) {
                    queue.offer(node.vertex);
                }
            }
        }

        return result;
    }

}

• 다른 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        StringBuilder sb = new StringBuilder();
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        int T = Integer.parseInt(reader.readLine()); // 테스트케이스 개수

        while (T-- > 0) {
            StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
            int N = Integer.parseInt(tokenizer.nextToken()); // 국가의 수
            int M = Integer.parseInt(tokenizer.nextToken()); // 비행기의 종류


            for (int i = 0; i < M; i++) {
                reader.readLine();
            }

            sb.append(N - 1).append("\n");
        }

        System.out.println(sb);
    }

}

• 어떻게 보면 어이가 없고 어떻게 보면 직관력이 부족한 문제 풀이였다.
• 처음에 문제 조건을 보고 MST를 떠올리긴 했으나 문제의 4번째 줄 "다른 국가로 이동할 때 다른 국가를 거쳐 가도(심지어 이미 방문한 국가라도)" 이 말을 너무 어렵게 해석하여 둘러 둘러 문제를 풀었다.
• BFS를 사용하여 문제를 맞추긴 했으나 시간이 너무 남들과 차이가 많이 나서 코드를 확인해 보니 그냥 N-1을 반환하고 있었다.
• 이게 뭔가 싶어 고민해보니, BFS로 문제를 풀 때에도 생각했던 부분인데, 가중치가 없는 그래프에서 어차피 최소 이동은 1이다. 다른 국가를 거쳐 가는 경우는 더 이상 갈 곳이 없어 뒤로 돌아오는 것을 뜻하는 것이었다.
• 여기까지 생각했으면 MST의 기본인 최소 스패닝 트리의 간선 수는 N-1인 성질을 통해 풀 수 있었을 것이나 미처 생각하지 못했다.