[Python][백준 1595] 북쪽나라의 도로

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

1595번: 북쪽나라의 도로

---

/*
신경써야 할 부분은 바로 :
1. 데이터 입력 try catch 문 활용해서 입력없음으로 오류 발생 방지
2. 최대 10000개 노드를 DFS 돌릴 시 시간초과 발생 
3. 따라서 가장 긴 거리를 찾는거니 가장 긴 거리를 가질 두 노드 중 하나를 구하고 
   해당 노드로 탐색을 돌리면 총 두번의 탐색만으로 가장 긴 도로를 찾을 수 있다.
*/

---

import sys
input = sys.stdin.readline
 
def dfs(n,s) :
    global result
    global temp
    for gr in graph[n] :
        if (n,gr[0]) not in visited :
            visited.append((n,gr[0]))
            visited.append((gr[0],n))
            dfs(gr[0],s+gr[1])
        result = max(result,s)
        if result == s :
            temp = n
    return

graph = {}
m = 0
result = 0

while 1:
    try:
        a, b, c = map(int, input().split())
        if a not in graph :
            graph[a] = []
        if b not in graph :
            graph[b] = []
            
        graph[a].append((b,c))
        graph[b].append((a,c))
        
        m = max(m,a)
        m = max(m,b)
        
    except: 
        break
        
if m == 1 or m == 0 :
    print(0)
    exit() 


visited = []
temp = 1
dfs(1,0)

result = 0
visited = []
dfs(temp,0)

print(result)

---

풀 때 어려웠던 점 또는 느낀점 :

공익 PS 3일차

완탐으로 해결 가능했다면 쉬웠겠지만

시간초과가 발생해서 당황했다가 힌트를 보고 푸는데 성공했다.

앞으로 이런류의 문제는 쉽게 풀 수 있을 것 같다

 

---

참고할만한 다른 사람 코드 :

import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)

def DFS(Node):
    visit[Node]=True
    for i,j in Tree[Node]:
        if not visit[i]:
            distance[i]+=distance[Node]+j
            DFS(i)


Tree=[ [] for _ in range(10001) ]

while True:
    try:
        u,v,k=map(int,input().split())
        Tree[u].append((v,k))
        Tree[v].append((u,k))
    except:
        break

visit = [False] * (10001)
visit[1]=True
distance=[0]*(10001)

DFS(1)
New_start=distance.index(max(distance))

visit = [False] * (10001)
visit[New_start]=True
distance=[0]*(10001)

DFS(New_start)
print(max(distance))

# https://velog.io/@030831/%EB%B0%B1%EC%A4%80-1595-%EB%B6%81%EC%AA%BD%EB%82%98%EB%9D%BC%EC%9D%98-%EB%8F%84%EB%A1%9C-Python

 

visit 체크를 시작 노드를 기반으로 하니 방문처리가 편해보인다.

리스트 생성 시 10000개 만들고 싶지 않아서 딕셔너리를 썼는데

괜히 코드만 길어진거 같기도 하다.