1167

날짜 : 2023. 05. 18

사용 언어 : python

 

문제

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

 

 

코드

import sys

sys.setrecursionlimit(int(10e6))


def dfs(now, cost):  # 현재 노드, 1부터 현재 노드까지의 cost
    for i in graph[now]:  # now 노드와 연결된 노드, now ~ 노드까지의 거리
        node, c = i[0], i[1]
        if not visited[node]:  # 방문하지 않은 경우
            visited[node] = True  # 방문처리
            dist[node] = (cost + c)
            dfs(node, cost + c)
    return


v = int(sys.stdin.readline())  # 정점의 개수
graph = [[] for _ in range(v + 1)]
dist = [0] * (v + 1)  # 노드 1에서부터 각 노드별 거리
visited = [False] * (v + 1)  # 방문처리
for _ in range(v):
    temp = list(map(int, sys.stdin.readline().split()))
    a = temp[0]
    for i in range(1, len(temp) - 2, 2):
        b, c = temp[i], temp[i + 1]
        graph[a].append([b, c])

dfs(1, 0)
visited[1] = True
last = dist.index(max(dist))  # 지름의 끝점 -> 기준점으로
dist = [0] * (v + 1)
visited = [False] * (v + 1)
visited[last] = True  # 기준점 방문처리
dfs(last, 0)
print(max(dist))
#print(dist)

 

 

풀이

- 트리의 지름(https://yhah.tistory.com/287)과 유사한 문제였다.

- 각 노드의 조건에 맞게 입력받은 후 우선 아무 노드를 기준으로 dfs를 수행해서 해당 노드에서 가장 떨어진 노드를 구한다.
- 그 노드는 트리의 지름에서의 끝점에 해당한다.

- 그리고 그 노드를 기준으로 dfs를 한번 더 실행하여 해당 노드에서 가장 떨어진 노드를 구한 후 해당 노드의 거리를 구했을 때의 값을 출력한다.

 

알게된 점

- 이 문제에서 두 가지 어려움이 있었다. 트리의 지름의 개념을 확실하게 알지 못했다는 점과 DFS를 사용하는데 있어서 유려하게 하지 못했다는 것이다.

- 트리의 지름에 관해서는 이전에 풀었던 문제의 코드를 참고하면서 풀었고, 각 노드별 간선과 cost를 입력받는 경우에는 visited, dist 리스트의 인덱싱을 똑바로 하지 못해서 계속 컴파일 에러가 발생했었다.

- 다행히 이를 잡아내고 문제를 풀어보니 곧바로 답이 출력됐다.

- 역시 골드2.. 더 노력해야겠다.

 

 

참고 사이트

-