문제https://www.acmicpc.net/problem/31476 31476번: :blob_twintail_thinking:첫째 줄에는 양갈래 굴의 방 중 가장 깊은 곳의 깊이 $D(1 \le D \le 12)$와 파손된 길목의 수 $N(0 \le N \le 2^D-2)$, 각 블롭 세력이 기본적으로 탐색하는 시간인 $U(1 \le U \le 100)$와 양갈래 블롭들이 갈라www.acmicpc.net트리를 레벨 순회, 중위순회 하는 문제였다. 양갈래 블롭같은 레벨은 가장 오래 걸린 시간이 소요된다.이때, 분기할 때마다 소요 시간이 T만큼 증가한다 (U+T, U+2*T, U+3*T...)포니테일 블롭중위순회 하면서 갔다가 돌아오는 길에도 탐색 시간이 U만큼 소요..
문제 https://www.acmicpc.net/problem/1765 1765번: 닭싸움 팀 정하기 1번 학생 혼자 팀, 2, 4, 6번 학생 셋이서 팀, 3, 5번 학생 둘이서 팀일 때, 팀의 개수가 최대이다. www.acmicpc.net 내 친구의 친구는 내 친구이다. 내 원수의 원수도 내 친구이다. 해당 조건에 맞게 짠 가장 많은 팀 수를 구하는 문제였다. 문제 풀이 Union-Find 알고리즘을 이용해 풀었다. 친구와 원소 그래프 벡터를 따로 만들었고 조건에 맞게 makeUnion 해주는 과정을 반복했다. 친구끼리는 makeUnion을 해줬으며 원수일 경우에는 해당 원수의 원수 리스트 모두에 대해 makeUnion을 해줬다. team 개수를 찾을 때에는 set을 이용해서 다른 parent를 가진..
문제 https://www.acmicpc.net/problem/2250 2250번: 트리의 높이와 너비 첫째 줄에 노드의 개수를 나타내는 정수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄마다 노드 번호와 해당 노드의 왼쪽 자식 노드와 오른쪽 자식 노드의 번호가 순서대로 주어진다. www.acmicpc.net 트리의 각 레벨의 양 끝 노드간의 거리 중 최댓값을 구하는 문제였다. 문제 풀이 처음에는 트리 노드에 달려 있는 노드들의 합으로 위치를 계산하려고 했는데, 중위순회를 하면 순회하는 순서가 위치가 될 것 같아서 다시 풀었다. 1번 노드의 parent를 계속 거슬러 올라가 루트 노드를 찾는다. 루트노드에서부터 중위순회를 돌려 각 노드의 위치를 찾는다. 트리를 레벨 별로 순회를 ..
