tree (2) 썸네일형 리스트형 [알고리즘/백준] 1967번 - 트리의 지름 카테고리 : Tree / DFS(그래프 탐색) 1967번 트리의 지름 - https://www.acmicpc.net/problem/1967 접근 방법 먼저 tree의 정보를 딕셔너리를 통해 저장해주었다. p는 부모 노드, c는 자식 노드, w는 가중치 정보이다. tree = defaultdict(list) n = int(input()) for _ in range(n - 1): p, c, w = map(int, input().split()) tree[p].append((c, w)) DFS를 통해 트리를 탐색한다. 루트 노드의 번호가 항상 1이라고 가정되어있기 때문에 항상 루트부터 시작할 수 있다. tree는 아까 저장해두었던 딕셔너리이고 i는 노드 번호이다. def DFS(tree, i): global r.. [알고리즘/백준] 11725번 - 트리의 부모 찾기 11725번 트리의 부모 찾기 - https://www.acmicpc.net/problem/11725 카테고리 : Tree / BFS(그래프 탐색) 접근 방법 노드 정보를 받을 때 트리 상에서 연결된 두 정점에 대해서 받게 된다. 따라서 정보를 받을 때 누가 부모인지 알 수 없어서 먼저 Tree를 2차원 리스트에 담아주었다. 노드 번호를 인덱스로 사용하기 위해 0번째 인덱스는 사용하지 않았다. 그리고 그래프처럼 각 정점에 대해 연결된 서로의 정점 정보를 모두 담아주었다. node = [[] for _ in range(N + 1)] for _ in range(N - 1): n1, n2 = map(int, input().split()) node[n1].append(n2) node[n2].append(n1) .. 이전 1 다음
