흙금이네 블로그

아이디어 트리를 중위 순회하여 노드들의 열 위치를 파악한 후, 각 레벨에서의 너비를 구한다. 풀이 #1 (Python) import sys input = sys.stdin.readline def solution(): def inorder(u, d): nonlocal cnt, D if D 0: inorder(left, d+1) cnt += 1 graph[d].append(cnt) if right > 0: inorder(right, d+1) N = int(input()) children = dict() is_root = [1]*(N+2) for _ in range(N): num, left, right = map(int, input().split()) is_root[left] = is_root[right] =..

아이디어 분할 정복으로 트리를 후위 순회한 결과를 출력한다. 풀이 #1 (Python) import sys def solution(): def postorder(order): if not order: return nonlocal idx, res temp = preorder[idx] left, right = order.split(preorder[idx]) idx += 1 postorder(left) postorder(right) res += temp cases = sys.stdin.readlines() for case in cases: preorder, inorder = case.split() idx = 0 res = '' postorder(inorder) print(res) solution() 풀이 #2..

아이디어 트리를 중위 순회하며 각 레벨의 빌딩 번호를 저장해 나간다. 풀이 #1 (Python) 지문에 깊이가 \(K\)인 완전 이진 트리는 총 \(2^{K}-1\)개의 노드로 이뤄져 있다는 설명은 포화 이진 트리에 대한 설명이다. def solution(): def traversal(s, e, i): m = (s+e)//2 tree[i].append(numbers[m]) if s >= e: return traversal(s, m-1, i+1) traversal(m+1, e, i+1) K = int(input()) tree = [[] for _ in range(K)] numbers = tuple(map(int, input().split())) traversal(0, len(numbers)-1, 0) fo..

아이디어 루트 노드부터 리프 노드까지의 길이 합이 홀수면 게임에서 이길 수 있다. 풀이 #1 (Python) BFS로 노드들을 탐색하면서 현재 노드가 리프 노드이고 길이가 홀수라면 결과를 반전한다. import sys input = sys.stdin.readline def solution(): N = int(input()) graph = [[] for _ in range(N+1)] for _ in range(N-1): a, b = map(int, input().split()) graph[a].append(b) graph[b].append(a) visited = [0]*(N+1) visited[1] = 1 queue = [1] is_win = False is_odd = False while queue: _..

아이디어 차례로 도시를 방문하며 새로 방문하는 도시의 부모 도시를 이전 도시 번호로 저장한다. 풀이 #1 (Python) 루트 도시는 0번 도시가 아니라 첫 번째로 방문하는 도시이고, 루트 도시에는 -1을 저장한다. def solution(): N = int(input()) numbers = tuple(map(int, input().split())) M = len(set(numbers)) parents = [-1]*M for i in range(1, N-1): if parents[numbers[i]] == -1: parents[numbers[i]] = numbers[i-1] parents[numbers[0]] = -1 print(M) print(' '.join(map(str, parents))) solu..

아이디어 맵을 이용해 각 클래스의 부모 클래스 정보를 저장하고, 부모 클래스를 탐색하며 형변환이 가능한지 확인한다. 풀이 #1 (Python) import sys input = sys.stdin.readline def solution(): N = int(input()) tree = dict() for _ in range(N-1): A, B = input().split() tree[A] = B A, B = input().split() a = A while a: a = tree.get(a, '') if a == B: print(1) return b = B while b: b = tree.get(b, '') if b == A: print(1) return print(0) solution() 풀이 #2 (Jav..

아이디어 각 노드의 자식 수를 구하되, 해당 노드가 왼쪽 서브 트리의 노드라면 1을 추가로 더한다. 풀이 #1 (Python) 중위 순회의 마지막 노드는 트리에서 가장 오른쪽에 있는 노드이다. 따라서 유사 중위 순회 방법에 따라 왼쪽 서브 트리에 속하는 노드는 모두 부모 노드로 이동하게 된다. DFS로 왼쪽 서브 트리에 속하는 노드는 자식 수+1, 나머지 노드는 자식 수를 결과값에 더해 나간다. import sys sys.setrecursionlimit(100002) input = sys.stdin.readline def solution(): def traversal(u, is_right): nonlocal res res += child[u]+1-is_right if tree[u][0] > 0: trav..

아이디어 노드를 지운 후 BFS로 자식이 없는 리프 노드의 개수를 센다. 풀이 2차원 리스트 tree에 지울 노드를 제외한 나머지 자식 노드의 번호를 자신의 부모 노드 인덱스에 맞춰 추가한다. BFS로 자식이 없는 리프 노드의 개수를 세어 결과값으로 출력한다. 지울 노드는 tree에 추가하지 않았으므로 탐색하지 않고 BFS가 종료된다. N = int(input()) tree = [[] for _ in range(N)] P = map(int, input().split()) r = int(input()) li = [] for idx, n in enumerate(P): if idx != r: if n >= 0: tree[n].append(idx) else: li.append(idx) res = 0 while ..