겜돌이의 개발일지

문제 백준 11725 트리의 부모 찾기 C++ 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 1이 루트기 때문에, 1에서 DFS나 BFS를 실행하면 된다. 해당 노드에 처음 방문했을 때, 그 전 노드가 부모가 된다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 #include #include #inc..

문제 백준 1967 트리의 지름 C++ 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 풀이 dfs를 사용합니다. 1. 1이 항상 루트 노드이므로, 1에서 가장 먼 노드를 찾습니다. 2. 가장 먼 노드에서 다시 dfs를 실행하여, 다른 가장 먼 노드 까지의 거리를 구합니다. 3. 그 거리가 트리의 지름이 됩니다. 트리의 지름을 출력합니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 3..

문제 백준 20364 20364번: 부동산 다툼 첫 번째 줄에 땅 개수 N과 꽉꽉나라에 사는 오리 수 Q가 공백으로 구분되어 주어진다. (2 ≤ N > N >> Q; for (int i = 0; i > num; int temp = num; bool canreach = true; stack st; //경로를 스택에 넣어줌 while (temp != 0) { st.push(temp); temp /= 2; } //스택 꺼내면서 경로확인 while (!st.empty()) { temp = st.top(); //경로의 해당 땅을 지나갈 수 없으면 if (check[temp] == true) { cout

문제 백준 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개입니다. 따라서 dp 배열을 1로 초기화해줍니다. 루트 노드부터 dfs를 실행하고, 서브 트리의 탐색이 모두 끝났다면 부모에게 자신의 서브 트리 값을 더해줍니다. 부모가 -1인 경우는 루트 노드이므로 더하지 않습니다. 예제를 보겠습니다. 숫자는 해당 정점에서의 서브 트리의 정점 개수이고, 괄호 안은 방문 순서..

문제 백준 1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 풀이 전형적인 트리 - dfs 문제입니다. 부모가 없는 노드(입력이 -1)를 루트 노드라고 하고, 루트 노드부터 dfs를 진행합니다. 이 때 제거하는 노드 처리가 중요한데, 루트 노드를 제거하였을 때는 0을 바로 출력해줍니다. 그 이외일 때는 제거한 노드를 기억하여, dfs를 실행할 때 방문하지 않습니다. 리프 노드는 자식이 없는 노드이므로 vector의 사이즈를 확인하여, 0이면 cnt를 ++해줍니다. 또한 제거된 노드 하나만을 자식으..