빵똥

https://www.acmicpc.net/problem/14267 14267번: 회사 문화 1 영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하 www.acmicpc.net 1. 접근 먼저 문제를 살펴보겠습니다. 문제 속 지문을 살펴보면 요구사항은 두 가지로 보입니다. 특정 직원을 칭찬하면 칭찬받은 직원의 부하 직원들도 같이 칭찬받는다. 칭찬에는 수치가 있으며 모든 칭찬이 끝나면 모든 직원들에 대해 누적 칭찬 치를 출력한다. 예제 입력을 예시로 각 직원을 노드로, 상하 관계를 부모 자식 관계로 나타낸 트리로 보면 다음과 같습니다. 그림을 보며 위 요구사항을 다시 정..

https://www.acmicpc.net/problem/15681 15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V) www.acmicpc.net 1. 접근 특이하게 힌트가 주어진 문제다. 트리의 정의에 대해 잘 모르시는 분은 힌트의 앞부분부터 읽고 이해한 후 문제에 접근하는 게 맞고 그게 아니라면 5번을 정점으로 트리 그림부터 보면 이해가 편하다. 문제는 간결하고 힌트는 이론부터 설명하기에 복잡해질 수 있는데 간단히 생각하기 위해 예제 입력을 하나하나 그림으로 뜯어보자. 첫째 ..

https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 1. 접근 일반적인 트리에서는 노드 제거 시 규칙(?)에 따라 자식 노드가 그 자리를 대체하는 방식이지만 문제에선 제거된 노드는 빈 채로 두어 가지 않는다. 즉, 입력 단계에서 루트가 -1로 주어지는 것만 염두에 두고 평소처럼 자식 노드들을 인접 리스트를 생성하되 마지막 입력인 지울 노드만 별도로 받았다가 탐색 전 경로를 끊어버리면 된다. 예제 입력 2번을 그림으로 보자 (1번 노드를 지울 ..