자바 - 백준 9372 / 상근이의 여행

백준 9372 / 상근이의 여행
실버4

구현 방법

"가장 적은 종류의 비행기", "갔던 나라 재방문 가능", "모든 나라 방문해야함" 보고 바로 스패닝 트리라는것을 눈치 챘습니다.
이 문제에서는 나라를 노드, 비행기를 간선이라고 생각하면 됩니다.
"그럼 모든 노드를 방문하면서 사이클이 존재하지 않는 그래프를 만들 때 필요한 간선의 수를 구하여라" 문제로 바뀌게 됩니다.
"가장 적은 종류의 비행기 == 사이클이 존재하지 않는 그래프"인 이유는 가장 적은 종류의 비행기라는 뜻은 간선을 최소화 하라는 뜻이 되기 때문입니다.


참고로 비행 스케줄은 연결 그래프라고 했기 때문에 모든 나라는 이어져 있다고 생각하면 됩니다.
현재 문제는 간선에 비용이 있지 않기 때문에 최소 스패닝 트리 알고리즘까지 적용할 필요가 없습니다.


따라서 트리의 특징을 이용하면 금방 풀립니다.
간선 = (노드 - 1) => 비행기 종류 = (나라 수 - 1)


최적화 전
처음에는 스패닝 트리인것까지만 눈치채고, 비용이 없으니까 그냥 BFS를 통해 비행기 종류를 카운트 했습니다. 하지만 이렇게 하면 카운트 하기 위해 계산이 들어가서 속도가 느렸습니다.

코드

트리의 특징 이용

import java.util.*;
import java.io.*;

/**
 * 백준 9372
 * 상근이의 여행
 * 실버4
 * https://www.acmicpc.net/problem/9372
 */
public class Boj9372_Tree {

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

        int T = Integer.parseInt(br.readLine());

        for(int t = 0; t < T; t++) {
            st = new StringTokenizer(br.readLine());

            int N = Integer.parseInt(st.nextToken()); // 국가의 수
            int M = Integer.parseInt(st.nextToken()); // 비행기의 종류

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

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

        System.out.print(sb);
    }
}

 

최적화 전 - BFS 이용

import java.util.*;
import java.io.*;

/**
 * 백준 9372
 * 상근이의 여행
 * 실버4
 * https://www.acmicpc.net/problem/9372
 */
public class Boj9372_BFS {

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

        int T = Integer.parseInt(br.readLine());

        for(int t = 0; t < T; t++) {
            st = new StringTokenizer(br.readLine());

            int N = Integer.parseInt(st.nextToken()); // 국가의 수
            int M = Integer.parseInt(st.nextToken()); // 비행기의 종류

            List<Integer>[] l = new ArrayList[N + 1];
            for(int i = 1; i <= N; i++)
                l[i] = new ArrayList<>();

            for(int i = 0; i < M; i++) {
                st = new StringTokenizer(br.readLine());

                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());

                l[a].add(b);
                l[b].add(a);
            }

            int cnt = 0;

            Queue<Integer> q = new LinkedList<>();
            q.add(1);
            boolean[] visited = new boolean[N + 1];
            visited[1] = true;
            while(!q.isEmpty()) {
                int cur = q.poll();

                for(int i : l[cur]) {
                    if(visited[i])
                        continue;

                    visited[i] = true;
                    cnt++;
                    q.add(i);
                }
            }

            sb.append(cnt).append("\n");
        }

        System.out.print(sb);
    }
}

느낀 점

개념을 이해하고 그걸 문제에 적용시키는 것이 꽤 어렵다는 것을 다시 느낍니다.