[BOJ][🟡4][백준#22865] 가장 먼 곳

문제 출처

BAEKJOON Online Judge #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$이 공백으로 구분되어 주어진다. 이 도로는 양뱡항 통행이 가능하다.

출력

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

제한

$ 1 ≤ N ≤ 100,000$ $N - 1 ≤ M ≤ 500,000$ $1 ≤ A, B, C, D, E ≤ N$ $1 ≤ L ≤ 10,000$

예제

입력

6
1 2 5
8
1 2 1
2 3 4
1 4 2
2 5 3
1 6 5
5 6 2
3 4 2
4 5 6

출력

3

My Sol

import sys
input = sys.stdin.readline
from heapq import heappop, heappush

def main():
    def make_rels():
        rels = [[] for _ in range(N+1)]
        M = int(input())
        for _ in range(M):
            u, v, w = map(int, input().split())
            rels[u].append((v, w))
            rels[v].append((u, w))
        return rels

    def find_max_len():
        mi, mv = 0, 0
        Ds = [find_max_len_sub(f) for f in friends]
        for i in range(1, N+1):
            smv = 1e9
            for j in range(3):
                smv = min(smv, Ds[j][i])
            if Ds[j][i] == 1e9: continue
            if smv > mv:
                mi, mv = i, smv
        return mi


    def find_max_len_sub(n):
        visited = [0]*(N+1)
        D = [1e9 for _ in range(N+1)]
        D[n] = 0
        H = [(0, n)]
        while H:
            d, u = heappop(H)
            if visited[u]: continue
            visited[u] = 1
            for v, w in rels[u]:
                if visited[v]: continue
                if D[v] > D[u]+w:
                    D[v] = D[u]+w
                    heappush(H, (D[v], v))
        return D

    N = int(input())
    friends = set(map(int, input().split()))
    rels = make_rels()
    return find_max_len()

print(main())

다익스트라 알고리즘을 사용하는 문제였다.

1. 입력을 받아 노드간 엣지를 저장한다. make_rels라는 함수를 작성해서 구현했다.
2. 3명의 친구들의 위치부터 시작하여 전체 노드의 최단거리를 구한다. find_max_len이라는 함수를 작성했는데, 이는 find_max_len_sub라는 하위 함수를 통해 friends의 각 시작점으로부터의 모든 최단거리를 받아, 모든 정점에서 거리를 체크하여 가장 먼 곳의 노드 인덱스를 반환하는 함수이다.
3. find_max_len_sub 함수는 인자로 받은 n으로부터 다익스트라 알고리즘을 실행하여 각 노드마다 최단거리를 저장한다.
4. main 함수는 find_max_len 함수의 반환값을 반환하고, 이를 출력하면 되겠다.

결과

맞았습니다!!