반응형 알고리즘/트리19 [백준][Python] 4256 트리 4256번: 트리 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 노드의 개수 n이 주어진다. (1 ≤ n ≤ 1,000) BT의 모든 노드에는 1부터 n까지 서로 다른 번호가 매겨져 있다. 다음 www.acmicpc.net 코드 import sys def post(preorder,inorder): if len(preorder) == 0: return elif len(preorder) == 1: print(preorder[0], end = ' ') return r_index = inorder.index(preorder[0]) # 루트노드가 inorder에서 몇 번째에 있는지 left_in = inorder[0:r_index] left_pre = preorder[1:len(.. 2022. 3. 11. [백준][Python] 9489번 사촌 9489번: 사촌 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 노드의 수 n과 사촌의 수를 구해야 하는 노드의 번호 k가 주어진다. (1 ≤ n ≤ 1,000, 1 ≤ k ≤ 1,000,000) 다음 줄 www.acmicpc.net 코드 import sys while 1: n,k = map(int,sys.stdin.readline().split()) if n == 0 and k == 0: break else: dic = {} n_list = list(map(int,sys.stdin.readline().split())) cnt = 0 parent = [] if len(n_list) > 1: next = n_list[1] parent.append(next) for i i.. 2022. 3. 10. [백준][Python] 3584번 가장 가까운 공통 조상 3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net 코드 import sys def parent(a): p = [] p.append(a) # 자기 자신도 조상으로 포함 for _ in range(N): if tree[a] == []: break else: p.append(tree[a]) a = tree[a] return p T = int(input()) for _ in range(T): N = int(input()) tree = [[] for _ in range.. 2022. 3. 8. [백준][Python] 15900번 나무 탈출 15900번: 나무 탈출 평소에 사이가 좋지 않던 성원이와 형석이가 드디어 제대로 한 판 붙으려고 한다. 성원이와 형석이 둘과 모두 똑같이 친한 인섭이가 대결 종목을 정해 가져왔다. 바로 '나무 탈출' 이라는 보드게 www.acmicpc.net 코드 import sys sys.setrecursionlimit(10**5) N = int(input()) tree = [[] for _ in range(N+1)] depth = [0 for _ in range(N+1)] visit = [0 for _ in range(N+1)] ans = 0 for _ in range(N-1): a,b = map(int,sys.stdin.readline().split()) tree[a].append(b) tree[b].append.. 2022. 3. 7. 이전 1 2 3 4 5 다음 반응형
