[BOJ] 9372. 상근이의 여행 (MST, BFS)

문제 풀러가기

 

1). 문제 읽기

상근이라는 친구가 N개의 나라를 모두 여행하고 싶어하는데. 돈을 절약하기 위해 최소한의 항공편을 사용해서 다녀오는 법을 알고싶어 합니다.

 

2). 문제접근

음.. 최대한 적은 항공편을 사용하면서 모든 나라를 여행한다. 여기서 나라를 그래프의 정점이라 생각하고 항공편을 간선이라고 생각하면, 최소 신장 트리를 구하라는 문제가 되는군요!

 

최소신장 트리에 대해서는? 아래에서 알려드릴게요~

 

3). 풀이방법

두 가지 풀이로 접근할 수 있을 것 같습니다.

1. BFS를 통해 갔던 나라는 다시 가지 않고 모든 나라를 방문해보기. 

  나라별로 존재하는 항공편을 리스트에 등록해두고

  어느 점에서 출발해도 좋으니 1번을 큐에 넣고 큐가 빌 때까지

  연결된 모든 정점을 방문해 나갑니다.

  최소값을 구해야하니 이미 방문 했던 지점은 구태여 가지 않는 게 좋을 것 같군요.

  BFS에서 제일 중요한 것은 방문을 언제 종료할 것이고 큐에 무엇을 넣을 것인가!

  큐에는 방문하는 나라를 집어넣고 종료는 모든 나라를 방문했을 때 끝내면 될 것 같습니다.

 

2. 최소 신장 트리의 간선 수는 항상 노드의 개수 - 1이다는 점 ( 이 문제에서는 N-1 )에 착안하여 N-1을 출력하기

 최소신장 트리란 무엇일까요?

정점 5개, 간선 4개로 이루어진 MST(Minimum Spanning Tree:최소신장트리)

 위의 그림처럼 우리말로 최소신장 트리라고 불리우는 MST(Minimum Spanning Tree)는 모든 간선 사이의 가중치가 최소이면서 사이클 없이 모든 정점이 연결되어 있는 트리를 말합니다.

 

이 문제에 대입해보면 모든 나라를 방문하면서 최소한의 비용을 지불하는 방법을 찾는 것이지요.

그런데 우리가 원하는 최소는 보통 이동거리인데. 이 문제는 간선의 개수를 최소화 시키라고 하고 있네요.

 

위의 그림을 보시면 알겠지만 MST의 간선의 개수는 항상 정점보다 한 개 적은 N-1개 입니다.

이 사실을 알았으니 간선을 직접 연결해 가지 않고도 문제를 풀 수 있겠죠?

 

5. 풀이

1). BFS

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class Main
{
    public static void main(String[] args) throws Exception
    {
        StringBuilder sb = new StringBuilder();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int tc = Integer.parseInt(br.readLine());
        for (int t = 1; t <= tc; t++)
        {
            String[] NM = br.readLine().split(" ");
            int N = Integer.parseInt(NM[0]); // 나라의 개수
            int M = Integer.parseInt(NM[1]); // 왕복 비행기 수

            ArrayList adj[] = new ArrayList[N+1];
            for (int i = 1; i <= N; i++) adj[i] = new ArrayList<>();
            for (int i = 0; i < M; i++)
            {
                String[] AB = br.readLine().split(" ");
                int a = Integer.parseInt(AB[0]);
                int b = Integer.parseInt(AB[1]);

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

            // 방문배열을 갖고 그래프를 탐색해보자.
            Queue q = new LinkedList<>();
            boolean[] visit = new boolean[N+1];
            int cnt = 0;   // 사용한 항공편
            q.add(1);

            while (!q.isEmpty())
            {
                int curNation = q.poll();

                if(!visit[curNation])
                {
                    // 방문 체크
                    visit[curNation] = true;
                    cnt++;

                    // 인접한 지점을 큐에 등록
                    for (int i = 0; i < adj[curNation].size(); i++)
                    {
                        int next = adj[curNation].get(i);
                        if(!visit[next]) q.add(next);
                    }
                }
            }
            sb.append(cnt-1).append("\n");
        }
        System.out.println(sb);
    }
}

2). MST 이론 적용

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main
{
    public static void main(String[] args) throws Exception
    {
        StringBuilder sb = new StringBuilder();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int tc = Integer.parseInt(br.readLine());
        for (int t = 1; t <= tc; t++)
        {
            String[] NM = br.readLine().split(" ");
            int N = Integer.parseInt(NM[0]); // 나라의 개수
            int M = Integer.parseInt(NM[1]); // 왕복 비행기 수

            // MST는 N-1개의 간선으로 이루어져 있다는 사실을 통해 답은 쉽게 구할 수 있다.
            for (int i = 0; i < M; i++)
            {
                br.readLine();
            }
            sb.append(N-1).append("\n");
        }
        System.out.println(sb);
    }
}