BOJ 20924번: 트리의 기둥과 가지

BOJ 20924번: 트리의 기둥과 가지

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

DFS를 기둥의 길이를 찾는 데 한번, 그리고 가지 길이의 최댓값을 찾는 데 또 한번 총 두 번을 써서 해결할 수 있는 문제였다.

인접리스트를 이용하여 데이터를 받았고, 스택(q)에 탐색노드와 해당 노드까지의 거리를 추가하는 방식으로 풀었다.

처음에 런타임에러(TypeError)가 나서 멘붕이었는데.. 기가노드가 탐색노드인 경우에 해당 노드에 연결된 노드가 2개면 잘못된 값을 출력하는 문제가 있었다. 그래서 해당 경우에 예외처리를 해 주니 통과하였다.

또한 함수 안에서 global 변수를 선언하면 해당 변수의 type이 'function'으로 나와서 max함수로 비교가 되지 않았다. 그래서 함수 내에서 global 변수를 0으로 한번 더 초기화시켜줬다.

import sys input = sys.stdin.readline N, R = map(int, input().split()) graph = [[] for _ in range(N+1)] for _ in range(N-1): a, b, d = map(int, input().split()) graph[a].append([b,d]) graph[b].append([a,d]) visit = [False]*(N+1) q = [] q.append([R,0]) visit[R] = True column = 0 branch = 0 #기둥까지의 거리 def col(): global column while(q): v = q.pop() if (len(graph[v[0]])>2): q.append([v[0],0]) break for i in graph[v[0]]: if (visit[i[0]]==False): visit[i[0]] = True q.append([i[0],v[1]+i[1]]) column = v[1] def branch(): global branch branch = 0 #안하면 max에서 오류 발생 while(q): v = q.pop() if (len(graph[v[0]])==1): branch = max(branch, v[1]) continue for i in graph[v[0]]: if (visit[i[0]]==False): visit[i[0]] = True q.append([i[0],v[1]+i[1]]) if (len(graph[R])==1): col() branch() print(column, branch)

from http://no-day-but-today.tistory.com/184 by ccl(A) rewrite - 2021-08-16 03:26:40