백준 14657번 준오는 최종인재야!!

문제 링크입니다: https://www.acmicpc.net/problem/14657

백준 1967번 트리의 지름(http://jaimemin.tistory.com/531)에서 한 단계 더 응용해야하는 문제였습니다.

따라서, DFS 함수 매개변수에 length라는 매개변수를 추가해서 동일한 지름이 있다면 가중치의 합이 더 작은 쪽을 선택하도록 했습니다.

알고리즘은 아래와 같습니다.

1. 우선, 루트에서 가장 멀리 떨어져 있는 노드를 찾습니다.

i) 루트 기준으로 가중치의 합이 제일 낮은 지점을 찾습니다.

2. 가장 멀리 떨어져 있는 노드 기준으로 가장 멀리 떨어져 있는 노드까지의 경로가 트리의 지름입니다.

i) 현재 저장된 지름보다 length가 더 클 경우 지름을 length로 초기화하고 가중치를 cost로 초기화합니다.

ii) 동일한 지름일 때, minCost가 cost보다 클 경우 minCost를 초기화합니다.

N개의 정점이 (N - 1)개의 양방향 간선으로 연결되어 있으므로 모든 노드가 루트가 될 수 있습니다.

따라서, 백준 1967번처럼 간단하게 1번 노드가 루트라고 가정했습니다.

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

using namespace std;

 

const int MAX = 50000 + 1;

 

int N, T;

int diameter; //지름

int farthestNode, minCost;

vector<pair<int, int>> graph[MAX]; //문제, 걸리는 시간

bool visited[MAX];

 

void DFS(int node, int length, int cost)

{

        //지름보다 더 길 경우

        if (diameter < length)

        {

                 farthestNode = node;

                 diameter = length;

                 minCost = cost;

        }

        //동일한 지름이지만 가중치가 더 작은 경우

        else if (diameter == length && minCost > cost)

        {

                 farthestNode = node;

                 minCost = cost;

        }

 

 

        //방문 표시

        visited[node] = true;

        for (int i = 0; i < graph[node].size(); i++)

        {

                 int next = graph[node][i].first;

                 int weight = graph[node][i].second;

 

                 if (!visited[next])

                         DFS(next, length + 1, cost + weight);

        }

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0); //cin 실행속도 향상

        cin >> N >> T;

 

        for (int i = 0; i < N - 1; i++)

        {

                 int A, B, C;

                 cin >> A >> B >> C;

 

                 //양방향

                 graph[A].push_back({ B, C });

                 graph[B].push_back({ A, C });

        }

       

        //루트에서 제일 멀리 있는 정점을 찾는데

        //경로가 가장 작은 가중치

        diameter = 1; //적어도 노드 하나

        DFS(1, 1, 0);

 

        //트리의 지름 구하기

        diameter = 1;

        minCost = 0;

        memset(visited, false, sizeof(visited));

        DFS(farthestNode, 1, 0);

 

        int residue = minCost % T == 0 ? 0 : 1;

        cout << minCost / T + residue << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~