백준 8872번: 빌라봉 (python)

by VICENTE97P4

Feb. 14, 2022, 3:57 p.m.

문제 링크: https://www.acmicpc.net/problem/8872

안녕하세요.  또 알고리즘 문제풀이로 돌아왔습니다.

재밌는 문제가 있어 포스팅하게 되었습니다.

파이썬으로 된 코드가 없는 것 같은데.. 잘 적어보겠습니다.

태초에 있었던 뱀과 캥거루의 이야기라고 성대하게 시작하는데 사실 그렇게 스케일이 크진 않습니다.

끊어진 포레스트들을 이었을 때, 두 빌라봉을 골랐을 때 최대가 되는 거리가 최소가 되는 경우를 찾아 출력하면 됩니다.

말로하니 조금 지저분한데 별건 아닙니다.

처음에는 뭘 어쩌란 거지.. 하는 생각이 듭니다.

일단 당연하게도 일일히 빌라봉들을 이어보는 방식은 시간복잡도 상 안될거고..

그럼 뭐.. 뭐지? 하는 생각이 듭니다.

일단, 포레스트를 하나의 기준으로 생각해봅시다.

두 포레스트를 잇는다고 했을 때, 가장 긴 두 빌라봉의 거리는 어떻게 될까요?

당장은 안 떠오를 수 있지만 차분히 생각해봅시다.

두 포레스트를 이으려면 각 포레스트 내에 있는 한 빌라봉을 골라서 이어줘야 합니다.

그럼 어떤 빌라봉을 고를까요?

고른 빌라봉에서 포레스트 내에서 다른 빌라봉까지의 최장거리가 가장 짧은 빌라봉을 고르면 됩니다.

예를 들어봅시다.

우측 하단에 있는 포레스트를 봅시다.

여기서 다른 포레스트랑 이을 빌라봉으로는 1번 빌라봉을 선택해야 합니다.

1번 빌라봉을 선택했을 경우, 포레스트 내에서 다른 빌라봉까지의 최장거리는 11번노드까지의 거리입니다.

이 때 거리는 3 + 7 = 10이죠.

만일 1번이 아닌 5번을 선택한다고 하면 최장거리는 9번 빌라봉까지의 거리로 7 + 5 = 12가 됩니다.

이 최장거리가 제일 짧은 빌라봉이 1번입니다.

일단 이어줄 대표 빌라봉을 구하는 방법은 나중에 알아보고 대표 빌라봉을 구했다고 칩시다.

그럼 대표 빌라봉을 구했는데 각 포레스트를 어떻게 이어줘야 할까요?

어떻게 이어줘야 두 빌라봉 사이의 최장거리가 가장 짧게 나올 수 있을까요?

그럼 일단 두 빌라봉 사이의 최장거리를 생각해봅시다.

1. 트리의 지름

포레스트를 잇지 않는다고 가정했을 때, 트리의 지름이 두 빌라봉 사이의 최장거리입니다.

그런데 포레스트끼리 이었다고 치더라도 그냥 트리의 지름이 두 빌라봉 사이의 최장거리일 수도 있습니다.

왜냐하면 이어줄 대표 빌라봉의 기준은 이었을 때 최장거리가 가장 짧은 빌라봉이기 때문에 트리의 지름은 따로 비교군에 넣어주어야 합니다.

예를 들어봅시다.

위 그림에서 우측 상단 포레스트(빌라봉 하나일 뿐이지만 따로 떨어져있으니 그 자체로 포레스트로 분류합시다.)랑

이어줄 경우 1번 빌라봉이랑 4번 빌라봉이랑 이어주게 되고, 1번 빌라봉이 속한 포레스트는 최장거리가 10이기 때문에

L이 1인 경우에 최장거리는 10 + 1 = 11이 됩니다.

하지만 정답은 그냥 1번 빌라봉이 있는 포레스트의 트리의 지름인 15입니다.

11번 ~ 9번 빌라봉 사이의 거리가 3 + 7 + 5 = 15로 더 길기 때문이죠.

이러한 경우가 있기 때문에 각 포레스트의 트리의 지름 중 가장 큰 값은 언제나 비교군에 들어있어야 합니다.

2. 성형으로 이어주기

성형(star topology)으로 이어주는 경우에 항상 최단거리를 만들어낼 수 있습니다.

당연한 이야기입니다. 최단거리가 되려면 연속적인 연결을 최대한 줄여야 하기 때문이죠.

그럼 구체적으로 어떻게 해야 할까요?

최장거리가 가장 긴 포레스트를 가운데에 둬야 합니다.

만일 최장거리가 가장 긴 포레스트를 중심에 놓지 않을 경우에는 다른 포레스트랑 이어지는 계산이 더욱 커지기 때문입니다.

위와 같이 이을 경우에는 최장거리가 16 + L이지만

위와 같이 이을 경우에는 16 + 2L이 최장거리가 되기 때문이죠.

즉, L이 한 번 더 더해지기 때문에 최장거리가 가장 긴 포레스트를 가운데에 둬야 합니다.

2-1, 그럼 최장거리가 가장 긴 포레스트를 가운데에 배치했다고 합시다.

그럼 가장 긴 포레스트  + L + 두 번째로 긴 포레스트의 합이 정답이 될 수 있습니다.

당연하죠.. 1등 + 2등의 길이가 1등 + 3등의 길이보다는 당연히 길테니까요..

1등 + 2등 : 10 + 6인 16이

1등 + 3등 : 10 + 3인 13보다 더 큼은 자명합니다.

그러므로 최장거리 1등 + L + 최장거리 2등이 비교군에 들어가야 합니다.

2-2. 그런데 한 가지 경우가 더 있습니다.

만일 L이 너무너무 커버려서 최장거리 1등 + L + 최장거리 2등 보다

1등을 포함하지 않더라도 L을 두 번 지나가는 것이 더 커버릴 수도 있습니다.

이 경우에는 2등과 3등을 포함하면 최장거리가 나옵니다.

L이 생각보다 커져서 16 + L보다. 9 + 2L이 더 커질 수도 있다는 말이죠.

L이 10이라고 가정하면 26보다 29가 더 크죠..

그래서 최장거리 2등 + 최장거리 3등 + 2L을 비교군에 포함시켜야 합니다.

비교해야하는 경우를 정리해봅시다.

1. 트리의 지름

2. 최장거리 1등 + 2등 + L

3. 최장거리 2등 + 3등 + 2L

자.. 그럼 마지막으로 구해야 하는..

포레스트끼리 이었을 때 포레스트 내에서의 최장거리..

이걸 어떻게 구할까요..?

이를 트리의 반지름이라고 합니다.

각 정점들에서의 가장 먼 거리들 중 최소가 되는 거리를 트리의 반지름이라 합니다.

이 트리의 반지름은 트리의 지름 위에 교점이 있습니다.(증명은 따로 찾아보시는 걸로..)

저는 처음에 아예 트리의 지름에 트리의 반지름이 포함되는줄 알아서 진짜 많이 틀렸습니다..

그게 아니고 교점만 트리의 지름 위에 있는 겁니다..

암튼 이 힌트가 있으면 트리의 반지름을 구할 수 있습니다.

트리의 지름을 구하고 그 위에 있는 노드들을 시점으로 한 최장거리를 구해주면 되니까요.

그럼 이제 코드를 봅시다.

import sys;

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
N, M, L = map(int, input().split())
graph = [[] for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    graph[a].append([b, c])
    graph[b].append([a, c])
dp = [0] * N


def DFS(prev, cur):
    global visited, dp

    visited[cur] = True

    node = cur
    cost = 0
    trace = []
    node_trace = [cur]
    for nex, weight in graph[cur]:
        if nex == prev:
            continue

        tcost, tnode, ttrace, tnode_trace = DFS(cur, nex)

        if cost < tcost + weight:
            cost = tcost + weight
            node = tnode
            ttrace.append(weight)
            trace = ttrace
            tnode_trace.append(cur)
            node_trace = tnode_trace

    dp[cur] = cost

    return cost, node, trace, node_trace


visited, length, ans = [False] * N, [], 0
for i in range(N):
    if visited[i]:
        continue

    w, node, trace, ntrace = DFS(-1, i)
    w, node, trace, ntrace = DFS(-1, node)
    ans = max(ans, w)

    s = sum(trace)
    cri = s
    acc = 0

    for i in range(len(trace)):
        acc += trace[i]
        cri = min(cri, max(dp[ntrace[i + 1]], s - acc))

    # w, node, trace, ntrace = DFS(-1, scan)
    length.append(cri)

if len(length) == 1:
    print(ans)
elif len(length) == 2:
    print(max(ans, length[-1] + length[-2] + L))
else:
    ans1, ans2, ans3 = 0, 0, 0
    for l in length:
        if ans1 <= l:
            ans3 = ans2
            ans2 = ans1
            ans1 = l
        elif ans2 <= l < ans1:
            ans3 = ans2
            ans2 = l
        elif ans3 <= l:
            ans3 = l

    print(max(ans, ans1 + ans2 + L, ans2 + ans3 + L + L))

생각보다 어렵습니다.

저도 다른 분들의 코드를 봤는데, 코드에 대한 설명이 안 적혀있어서 정말 이해하기 힘들었습니다.

하나씩 봅시다.

dp = [0] * N


def DFS(prev, cur):
    global visited, dp

    visited[cur] = True

    node = cur
    cost = 0
    trace = []
    node_trace = [cur]
    for nex, weight in graph[cur]:
        if nex == prev:
            continue

        tcost, tnode, ttrace, tnode_trace = DFS(cur, nex)

        if cost < tcost + weight:
            cost = tcost + weight
            node = tnode
            ttrace.append(weight)
            trace = ttrace
            tnode_trace.append(cur)
            node_trace = tnode_trace

    dp[cur] = cost

    return cost, node, trace, node_trace

dp는 각 서브트리의 최대 높이를 저장합니다. 나중에 트리의 반지름을 구할 때 사용하죠.

node는 트리의 지름에 있는 노드들을 저장합니다.

trace는 트리의 지름에 있는 간선의 길이를 저장합니다.

cost는 서브트리의 높이 중 가장 긴 값입니다.

DFS 코드 자체는 그냥 서브트리의 높이 구하는 코드와 비슷하고 중간에 trace 로직만 추가된 것이기 때문에

찬찬히 읽어보시면 크게 어렵지 않으실 겁니다.

visited, length, ans = [False] * N, [], 0
for i in range(N):
    if visited[i]:
        continue

    w, node, trace, ntrace = DFS(-1, i)
    w, node, trace, ntrace = DFS(-1, node)
    ans = max(ans, w)

    s = sum(trace)
    cri = s
    acc = 0

    for i in range(len(trace)):
        acc += trace[i]
        cri = min(cri, max(dp[ntrace[i + 1]], s - acc))

    # w, node, trace, ntrace = DFS(-1, scan)
    length.append(cri)

length는 각 포레스트의 최장거리를 저장합니다.

ans는 포레스트의 트리의 지름 중 가장 큰 값입니다.

DFS를 두 번 하여 트리의 지름을 구합니다.

(트리의 지름은 아무 노드에서 가장 높이기 큰 노드로 한 번,

그 노드에서 또 높이가 가장 큰 노드로 한 번 DFS 하면 구할 수 있습니다.)

이때 두 번째 DFS의 결과로 나온 ntrace와 trace에는 트리의 지름에 있는 노드와 간선의 길이가 저장되어 있습니다.

그리고 결과로 나온 w가 트리의 지름이므로 ans값에 갱신해줍시다.

    s = sum(trace)
    cri = s
    acc = 0

    for i in range(len(trace)):
        acc += trace[i]
        cri = min(cri, max(dp[ntrace[i + 1]], s - acc))

이 부분이 좀 어려울 수 있을 것 같습니다.

s는 트리의 지름, cri는 criteria, 즉, 비교 기준으로, 트리의 지름을 구하기 위한 변수입니다.

acc는 trace에 있는 각 간선을 더해나가는 축적값입니다.

아니 dp에 각 노드의 서브트리의 최대 높이가 저장되어 있는데 트리의 지름(s)에서 왜 trace의 축적값을 빼냐?

이렇게 생각하실 수 있습니다.

그 이유는 트리의 지름 한 쪽 끝에서 그 노드까지의 거리까지 포함해줘야 최장거리를 바르게 구할 수 있기 때문입니다.

예시를 봅시다.

높이가 10인 노드부터 시작했다고 했을 때, 높이가 3인 노드를 보면

최장거리는 3이 아닌 7입니다. 이를 구하기 위해서 트리의 지름(s)에서 trace의 축적값을 빼주는 것이죠.

dp에는 서브트리의 최대높이만 저장되어있기 때문에 반드시 반대 방향으로의 거리도 고려해줘야 합니다.

이 과정을 위해 ntrace, trace, s값을 알 필요가 있어 DFS 코드가 괴랄하게 되었습니다.

if len(length) == 1:
    print(ans)
elif len(length) == 2:
    print(max(ans, length[-1] + length[-2] + L))
else:
    ans1, ans2, ans3 = 0, 0, 0
    for l in length:
        if ans1 <= l:
            ans3 = ans2
            ans2 = ans1
            ans1 = l
        elif ans2 <= l < ans1:
            ans3 = ans2
            ans2 = l
        elif ans3 <= l:
            ans3 = l

    print(max(ans, ans1 + ans2 + L, ans2 + ans3 + L + L))

이제 length에는 트리의 반지름들이 들어있으므로

1번, 2번 3번 경우를 모두 고려해줍시다.

if문은 length의 원소가 1개, 2개만 있을 경우의 예외처리를 위한 것입니다.

그냥 sort를 해도 통과는 하는데, 저는 O(N)을 맞추고 싶어서 

트리의 반지름 1, 2, 3등을 일일히 구해줬습니다.

참고로 트리의 지름이 같은 경로가 2개가 있어도 상관없습니다.

어차피 교점은 무조건 트리의 지름에 생기고, 갈라지는 쪽은 짧은 쪽이라 정답에는 지장이 없습니다.

아이디어도 어렵고, 트리의 반지름이라는 개념도 어렵고, 구현도 까다로운 문제였습니다.

그래도 생각을 많이 해볼 수 있었고, 새로운 개념을 배운 문제였습니다.

알고리즘 문제풀이.. 재밌네요.. 이걸 10년만 일찍 알았어도..

참 아쉽습니다. ICPC도 정말 나가보고 싶은데 현실이 녹록치 않네요.

제가 지난 10년동안 배워온 것들은 무슨 의미일까요..

이걸 일찍 알고 준비해온 사람들이 부럽습니다..

넓은 시야를 가지고 진로를 잘 설정했어야 했는데.. 저는 눈 앞에 있는 국영수과가 제일 중요한줄 알았죠..

그땐 하고 싶은 것들도 참으며 열심히 공부하면 지금쯤 후회없이 잘살줄 알았는데..

잘사는 것도 아니고, 후회는 넘치고.. 당장 취업도 불투명하고..

아쉬운 지난날이지만 뭐 어쩌겠습니까.. 남은 날들을 잘 살아봐야죠..

아무튼 유달리 아쉬움이 많이 남는 하루입니다.