[BOJ/Silver 2] 백준 18126 너구리 구구(C++)

문제 링크

https://www.acmicpc.net/problem/18126

18126번: 너구리 구구

 

문제

텔레토비 동산에 사는 너구리 구구는 입구, 거실, 주방, 안방, 공부방, 운동실, 음악실, 음식 창고 등 N개의 방을 가지고 있다. 입구를 포함한 모든 방은 1부터 N까지의 번호가 있고, 입구는 1번이다.  구구의 집으로 들어가는 입구는 한 개이며 입구과 모든 방들은 총 N-1개의 길로 서로 오고 갈 수 있다.

구구는 스머프 동산에서 멜론아 아이스크림을 발견했다. 구구는 무더운 여름 햇살을 피해 최대한 입구에서 먼 방에 아이스크림을 숨기려고 한다.

구구가 집 입구에서 멜론아 아이스크림을 숨기려고 하는 방까지 이동하는 거리를 구하여라.

입력

첫째 줄에 정수 N(1 ≤ N ≤ 5,000)이 주어진다.

다음 N-1개의 줄에 구구의 집의 모든 길의 정보가 정수 A, B, C(1 ≤ A, B ≤ N, 1 ≤ C ≤ 1,000,000,000)로 주어진다.

A번 방과 B번 방 사이를 양방향으로 연결하는 길의 길이가 C임을 의미한다.

출력

구구가 집 입구에서 멜론아 아이스크림을 숨기려고 하는 방까지 이동하는 거리를 구하여라.

예제 입력 1

4
1 2 3
2 3 2
2 4 4

예제 출력 1

7

알고리즘 분류

• 그래프 탐색

풀이

BFS로 1번 방부터 모든 방까지의 최단 거리를 기록하고, 1번 방에서 N - 1개의 방까지 도달하는 데 필요한 이동 거리의 최댓값을 출력한다.

길 하나의 길이가 10억이고, 방은 최대 5,000개까지 존재하므로 특정 방까지의 이동 거리는 최대 5^12까지이므로 long long을 사용한다.

코드

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#define MAX 5001
#define INF 5e12+1
#define LL long long
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int N, A, B;
LL C;
vector<pair<int, LL> > Edge[MAX];
LL Dist[MAX];
LL Answer;

void init() {
    for (int i = 0; i < MAX; i++) {
        Dist[i] = INF;
    }
}

void input() {
    cin >> N;
    for (int i = 0; i < (N - 1); i++) {
        cin >> A >> B >> C;
        Edge[A].push_back(make_pair(B, C));
        Edge[B].push_back(make_pair(A, C));
    }
}

void BFS() {
    Dist[1] = 0;
    queue<pair<int, LL> > Q;
    Q.push(make_pair(1, 0));

    while (!Q.empty()) {
        int NowX = Q.front().first;
        LL NowC = Q.front().second;
        Q.pop();

        for (int i = 0; i < Edge[NowX].size(); i++) {
            int NextX = Edge[NowX][i].first;
            LL NextC = Edge[NowX][i].second;
            if (Dist[NextX] > NowC + NextC) {
                Dist[NextX] = NowC + NextC;
                Q.push(make_pair(NextX, Dist[NextX]));
            }
        }
    };
}

void settings() {
    BFS();
    for (int i = 1; i <= N; i++) {
        Answer = max(Answer, Dist[i]);
    }
}

void find_Answer() {
    cout << Answer << "\n";
}

int main() {
    FASTIO
    init();
    input();
    settings();
    find_Answer();

    return 0;
}