[백준] 22865번 : 가장 먼 곳 (C++)

22865번 : 가장 먼 곳

---

문제)

 N개의 땅 중에서 한 곳에 자취를 하려고 집을 알아보고 있다. 세 명의 친구 A, B, C가 있는데 이 친구들이 살고 있는 집으로부터 가장 먼 곳에 집을 구하려고 한다.

이때, 가장 먼 곳은 선택할 집에서 거리가 가장 가까운 친구의 집까지의 거리를 기준으로 거리가 가장 먼 곳을 의미한다.

예를 들어, X 위치에 있는 집에서 친구 A, B, C의 집까지의 거리가 각각 3, 5, 4이라 가정하고 Y 위치에 있는 집에서 친구 A, B, C의 집까지의 거리가 각각 5, 7, 2라고 하자.

이때, 친구들의 집으로부터 땅 X와 땅 Y 중 더 먼 곳은 땅 X이다. 왜냐하면 X에서 가장 가까운 친구의 집까지의 거리는 3이고, Y에서는 2이기 때문이다.

친구들이 살고 있는 집으로부터 가장 먼 곳을 구해보자.

 

 

 

입력 :

첫번째 줄에 자취할 땅 후보의 개수 N이 주어진다.

2번째 줄에는 친구 A, B, C가 사는 위치가 공백으로 구분되어 주어진다. 이때 친구들은 N개의 땅 중 하나에 사는 것이 보장된다. (같은 위치에서 살 수 있다.)

3번째 줄에는 땅과 땅 사이를 잇는 도로의 개수 M이 주어진다.

그 다음줄부터 M + 3번째 줄까지 땅 D, 땅 E, 땅 D와 땅 E와 사이를 연결하는 도로의 길이 L이 공백으로 구분되어 주어진다. 이 도로는 양뱡항 통행이 가능하다.

 

 

 

출력 :

친구들이 살고 있는 집으로부터 가장 먼 곳의 땅 번호를 출력한다. 만약 가장 먼 곳이 여러 곳이라면 번호가 가장 작은 땅의 번호를 출력한다.

 

 

 

 

풀이)

 

// 22865. 가장 먼 곳
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
 
using namespace std;
 
int n, m;
vector<vector<pair<int, int>>> vec;
vector<int> _friend;
 
long long dist[100010];
 
priority_queue<pair<int, int>
    , vector<pair<int, int>>
    , greater<pair<int, int>>> pq;
 
void dijkstra(int s)
{
    // 일반적인 다익스트라 구현
    while (!pq.empty()) pq.pop();
    dist[s] = 0;
    pq.push(make_pair(0, s));
 
    while (!pq.empty())
    {
        long long d = pq.top().first;
        int cur = pq.top().second;
        pq.pop();
 
        if (dist[cur] < d) continue;
 
        for (int i = 0; i < vec[cur].size(); i++)
        {
            long long nd = d + vec[cur][i].second;
            int nxt = vec[cur][i].first;
 
            if (dist[nxt] > nd)
            {
                dist[nxt] = nd;
                pq.push(make_pair(nd, nxt));
            }
        }
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n;
    fill(&dist[0], &dist[100009], LONG_MAX);
    vec.resize(n + 1, vector<pair<int, int>>());
 
    _friend.resize(3, 0);
    for (auto& ele : _friend) cin >> ele;
 
    cin >> m;
    int a, b, c;
    for (int i = 0; i < m; i++)
    {
        cin >> a >> b >> c;
        // 양방향 간선
        vec[a].push_back(make_pair(b, c));
        vec[b].push_back(make_pair(a, c));
    }
 
    for (int i = 0; i < 3; i++)
    {
        // 각 친구들에 대해서 다익스트라를 실행한다.
        dijkstra(_friend[i]);
    }
 
    // 1번부터 n번까지의 최댓값을 찾는다.
    int max_num = *max_element(&dist[1], &dist[n + 1]);
 
    // 최댓값을 가지는 땅 중 가장 작은 땅의 번호를 출력한다.
    for (int i = 1; i < n + 1; i++)
    {
        if (dist[i] == max_num)
        {
            cout << i;
            break;
        }
    }
 
    return 0;
}
 

---

출처 : https://www.acmicpc.net/problem/22865 

22865번: 가장 먼 곳