[백준] 1167 - 트리의 지름

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

1167번: 트리의 지름

문제 한줄 이해

- 트리의 지름 구하기

생각난 풀이

https://9-bin.tistory.com/42 지난번에 풀이했던 문제와 같았다. 그래서 이번에 dfs를 활용해 풀이했다.

문제를 읽고 생각난 필요한 조건들

1. 간선의 정보가 입력되고 마지막에 -1이 입력되면 다음으로 넘어간다.

-> 원래는 간선의 갯수만큼 입력 받으면 됐는데... 리스트 형식으로 맨 뒤에가 -1이라고 한다 ...

->그래서 입력받을 때 큐에 형태로 입력 받아서 맨앞에 있는걸 popleft해서 현재 담을 노드로 지정하고 나머지 요소를 가지고 for문을 2칸씩 뛰면서 값을 추가해줬다.

-> 2칸씩 뛰는 이유는 맨앞에 있는 현재 노드 번호를 제외하고 (노드번호, 값)의 형태로 들어오기 때문에 2칸씩 잘라서 보면 되고 그 값이 -1이 아니면 값을 추가해주면 된다!

 

2. dfs를 통해 트리의 지름 구하기 (위에 문제에서 푼 기억이 나서 금방 해결했다.)

->아이디어는 바로 트리의 지름은 결국 노드들 중 가장 멀리있는 노드 2개다. 이때 어떤 노드든 트리의 지름이 되는 노드 2개중 하나는 가장 멀리있는 노드가 된다.

->그래서 임의의 노드 한개를 골라 가장 멀리 있는 노드를 구하고 그 노드를 기준으로 또 가장 멀리있는 노드의 거리값을 구한다!

 

import sys
from collections import deque

v = int(sys.stdin.readline())
graph = [[] for i in range(v+1)]

for i in range(v):
    wlist = deque(map(int,sys.stdin.readline().split()))
    a = wlist.popleft()
    for j in range(0,len(wlist),2):
        if wlist[j] != -1:
            graph[a].append((wlist[j],wlist[j+1]))
            
def dfs(nowv,dis):
    global ans
    global max1
    if ans < dis:
        ans = dis
        max1 = nowv
        
    #현재 노드의 연결된 정보를 가져와서 거리와 다음 노드를 가지고 재귀
    for i in graph[nowv]:
        if visited[i[0]] == False:
            visited[i[0]] = True
            dfs(i[0],dis + i[1])
    #더이상 탐색할 노드가 없다면 함수 종료
    return


ans = 0
max1 = 0
#먼저 임의의 점을 잡아서 가장 멀리있는 노드 구하기
visited = [False] *(v+1)
visited[1] = True 
dfs(1,0)

#가장 멀리 있던 노드를 기준으로 다시 한번 가장 멀리있는 노드 찾아서 거리 구하기
ans = 0
visited = [False] *(v+1)
visited[max1] = True
dfs(max1,0)
print(ans)

알고리즘을 풀어가면서 느낀건데 확실히 수학공부를 하는 거와 같은거 같다.

이유는 수학도 공식을 공부하고 이를 토대로 문제에 적용하고 -> 자료구조, 알고리즘을 공부해서 문제에 적용하고

                      다양한 문제를 풀어보면서 아이디어 기르기 -> 이번 문제도 이전에 푼 문제가 응용된 것

그래서 결론은 포기하지말고 꾸준히 문제를 해결해나가자!!!!!!!!!!!!!!!!!