ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 9372.상근이의 여행
    알고리즘/백준 BAEK JOON 2020. 8. 20. 00:36

    이번에 풀어볼 문제는 백준 9372의 상근이의 여행이라는 문제이다.

     

    9372번: 상근이의 여행

    문제 상근이는 겨울방학을 맞아 N개국을 여행하면서 자아를 찾기로 마음먹었다.  하지만 상근이는 새로운 비행기를 무서워하기 때문에, 최대한 적은 종류의 비행기를 타고 국가들을 이동하려�

    www.acmicpc.net

    Spanning Tree에 대해서 공부할 수 있는 문제이며 최소 신장 트리(MInimum Spanning Tree)까지 공부할 수 있었다.

    Spanning Tree : 방향이 없는 그래프에서 모든 정점들을 연결함과 동시에 순환경로가 없는 형태를 의미한다.

    => 만약 이와 같은 상황에서 가중치가 포함되고 최소 가중치만을 이용하여 연결하는 경우를 최소 신장 트리라고 한다.

    이 문제를 잘 읽어보면 일단 최소 신장 트리 문제는 아니다. 간선에 대한 가중치에 대한 언급이 없기 때문이다.

     

     

     


     

    * 참 고

    최소 신장 트리를 구하는 알고리즘에는 대표적으로 크루스칼 알고리즘, 프림 알고리즘이 있다.

    1. 크루스칼 알고리즘 (간선 기반) O(elog₂e)

    탐욕적인 방법을 이용한 것으로 특징으로는 간선을 오름차순으로 정렬한 뒤 최소 간선 부터 선택한다.

    주의할 점은 사이클이 형성되면 안된다.

     

    2. 프림 알고리즘 ( 정점 기반 ) O(n^2)

    시작 정점에서 시작하여 인접간 정점과의 간선의 가중치가 적은 간선부터 선택하여 진행한다.

     


     

    또한 해당 문제 조건에서 주어진 비행 스케줄은 항상 연결 그래프라고 했다.

    => 즉, 모든 정점들이 연결되어있다고 했다.

    => 모두 연결된 상태에서 최소의 비행기 종류를 물어봤기 때문에 신장 트리라고 생각하면 된다.

    => 그러므로 정점 - 1 이 정답이 된다

    한마디로 문제를 풀 필요가 없이 그냥 정점 - 1 이 정답이다...

    그냥 입력받은 받되 정점 개수 - 1 을 출력해주면 된다!

     


     

    < Code 설명 >

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20

    #pragma
     warning(disable:4996)
    #include <iostream>
     
    using namespace std;
     
    int T, N, M;
    int main() {
        freopen("9372.txt""r", stdin);
        cin >> T;
        for (int z = 1; z <= T; z++){
            cin >> N >> M;
            for (int i = 0; i < M; i++){
                int a, b;
                cin >> a >> b;
     
            }
            cout << N-1 << endl;
        }
        return 0;
    }
    cs
    반응형

    '알고리즘 > 백준 BAEK JOON' 카테고리의 다른 글

    19238.스타트 택시  (0) 2020.08.30
    1197.최소 스패닝 트리  (0) 2020.08.20
    1932.정수 삼각형  (0) 2020.08.19
    1074.Z  (0) 2020.08.15
    15686.치킨배달  (0) 2020.08.11

    댓글

Designed by Tistory.