평범한 필기장

https://www.acmicpc.net/problem/9372 9372번: 상근이의 여행 첫 번째 줄에는 테스트 케이스의 수 T(T ≤ 100)가 주어지고, 각 테스트 케이스마다 다음과 같은 정보가 주어진다. 첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가 www.acmicpc.net Idea : 트리를 BFS방식 (BFS 방식이 정확하게 맞는진 모르겠지만,,,)으로 모든 점을 탐색해서 몇번만에 탐색이 완료되는지를 세어봤다. 2차원 빈 리스트를 만들어서 각 인덱스의 빈 리스트에 그 인덱스 번호와 연결된 번호를 리스트에 넣어 graph를 만들었다.빈 큐를 만들어서 특정 점과 연결된 점들을 넣을 공간을 만들었고, 특정 점을 방문 했는지를 체크하..

이 문제를 보고 단절선을 찾는 함수 단절점을 찾는 함수를 각각 만들어보려 했는데 도저히 생각이 나지 않았다. 그렇게 문제를 켜두고 생각을 해보니 트리에서 어떤 간선을 없애도 항상 2개의 트리로 나눠진다는 것을 떠올렸고 트리의 끝점 즉, 자식이 없는 노드를 제외하고 나머지 노드를 제거하면 트리는 2개의 트리로 항상 나눠 진다는 것을 생각해냈다. 그래서 처음에 graph를 만들 때 빈 리스트가 (노드의 개수 + 1) 개인 2차원 빈 리스트를 만들고 각 리스트에 연결된 노드를 넣었다. (1번 노드와 3번 노드가 연결되어 있으면 1번째 리스트에 3을 넣고 3번째 리스트에 1을 넣는 방식) 그리고 간선을 없앤다고 하면 항상 yes를 출력하게 하고 노드를 없애면 그 노드가 자식이 없는 마지막 노드인지를 확인하고 마..

이 문제를 보면 입력의 첫째 줄에는 완전 이진 트리의 깊이가 나와있고 두번째 줄에는 방문 순서 대로 빌딩의 번호가 나와있습니다. 이 문제에서는 기준 노드를 기준으로 좌측 자식 노드를 먼저 방문하고 기준 노드를 방문하고 우측 자식 노드를 방문합니다. (inorder algorithm) 그래서 일단 저는 깊이 만큼의 빈 리스트가 있는 2차원 빈 리스트인 answer list를 만들고 각 레벨에 있는 숫자들을 빈 리스트의 인덱스에 맞게 넣을려고 했습니다. 완전 이진 트리이기 때문에 루트부터 0번째 리스트에 넣으려 했습니다. 이 완전 이진 트리의 루트는 주어진 리스트의 중앙 인덱스에 위치한 값이겠죠? 왜냐하면 완전 이진 트리 특성상 이진 트리가 완전히 꽉 채워져 있기 때문에 루트 노드를 기준으로 좌우의 노드 개..