WannaBeDeveloper

1068번: 트리 www.acmicpc.net 이 문제는 트리에서 노드 하나를 지웠을 때 남은 트리에서 리프 노드의 개수를 구하는 문제이다. 이 문제는 트리를 각 노드의 부모 노드를 표현하는 배열로 나타내기 때문에 노드 하나를 단순히 제거하기는 쉽지 않다. 노드 하나를 제거할 때 그 노드의 자식 노드 역시 제거되기 때문에, 이를 부모 노드를 표현하는 배열에 반영해야 한다. 노드 하나를 제거하는 함수를 구현해보자. 우선 각 노드의 부모 노드를 표현하는 배열을 parents라 하고, 노드 u를 제거하는 경우 이를 parents 배열에는 parents[u] = -2로 반영한다고 하자. 그러면 노드 v를 제거하는 함수에서는 우선 parents[v]를 -2로 하고, 모든 노드를 순회하면서 만약 부모 노드가 v인 ..

2644번: 촌수계산 www.acmicpc.net 이 문제는 여러 사람들에 대한 부모 자식 관계가 주어졌을 때 주어진 두 사람의 촌수를 계산하는 문제이다. 단, 각 사람의 부모는 최대 한 명만 주어진다. 이를 해결하기 위해서는 문제에서도 직관적으로 알 수 있듯이 각 사람들을 하나의 노드로 하고 부모 자식 관계는 간선으로 표현한 트리를 만들면 된다. 특히 문제의 조건 중에 각 사람의 부모가 최대 한 명이라는 조건에 의해 각 노드마다 부모 노드는 두 개 이상 될 수 없어 이를 구현하는데 문제가 없다. 트리는 각 노드마다 부모 노드의 번호를 저장하는 배열 parent를 만들어 구현한다. 예를 들어 n 9일 때 부모 자식 관계가 주어질 때 1 2라는 input이 주어지면 2의 부모가 1이라는 의미이므로 pare..

1949번: 우수 마을 www.acmicpc.net 이 문제는 기존의 트리의 독립집합을 구하는 문제에 '독립집합에 들어가지 않는 정점은 적어도 하나의 독립집합 내 정점과 인접해야 한다'는 추가 조건이 붙은 경우이다. 이 조건을 만족시키기 위해서 기존의 트리의 독립집합을 구하는 알고리즘에 각 정점 u에 대해 u를 루트로 하는 서브트리에서 u를 포함하지 않는 독립집합의 정점들의 가중치 합의 최댓값을 구할 때 u의 자식 노드 중 자식 노드 자신을 포함하는 독립집합을 적어도 한 번 선택했는지를 boolean 값으로 나타내는 배열 near_good을 추가한다. 기존 문제에서는 dynamic programming 과정에서 인자로 주어진 노드가 독립집합에 포함되지 않을 경우 자식 노드가 독립집합에 포함되는지 안 되는..

2533번: 사회망 서비스(SNS) www.acmicpc.net 이 문제는 트리로 나타낼 수 있는 친구 관계에서 모든 개인이 새로운 아이디어를 수용하기 위한 최소 얼리 어답터의 수를 구하는 문제로, 얼리 어답터가 아닌 사람이 새로운 아이디어를 수용하기 위해서는 그 사람과 인접한 사람들이 모두 얼리 어답터여야 한다. 이 문제는 이전의 트리의 독립집합 문제와 유사한 방법으로 해결할 수 있다. 다만, 각 노드마다 자신이 얼리 어답터가 되는 경우와 그렇지 않은 경우로 나눠서 dynamic programming을 적용한다. 각 노드 u마다 자신이 얼리 어답터가 되는 경우 u를 루트로 하는 서브트리에서 u의 각 자식 노드가 얼리 어답터가 되든 안 되든 상관없으므로 두 경우 중 최소가 되는 얼리 어답터의 수를 u의 ..

15681번: 트리와 쿼리 www.acmicpc.net 이 문제는 루트 있는 트리가 주어졌을 때 임의의 정점을 루트로 하는 서브트리에 속한 정점의 수를 출력하는 문제이다. 우선 트리 내의 서열을 고려한 그래프 탐색을 위해서는 DFS를 이용해야 한다. 왜냐하면 DFS의 경우 함수를 재귀적으로 호출할 때 자식 노드와 부모 노드가 명확히 결정되기 때문이다. 예를 들어 루트 노드에 대해 DFS를 호출하면 루트 노드의 자식 노드에 대해 DFS를 재귀적으로 호출하고, 자식 노드에 대한 DFS 내에서는 그 자식 노드의 자식 노드들에 대해 DFS를 재귀적으로 호출한다. 그리고 이 문제에서 얻고자 하는 것은 임의의 노드들에 대해 해당 노드가 루트가 되는 서브트리의 정점의 개수인데, 주어지는 노드의 개수가 10^5개까지 ..

4803번: 트리 www.acmicpc.net 이 문제는 그래프가 주어질 때 그래프 내에 트리가 몇 개가 있는지 세는 문제이다. 이 문제를 해결하기 위해서는 트리를 찾는 방법을 생각할 필요가 있다. 트리는 사이클이 없는 연결된 요소이므로, 그래프 탐색을 이용해 연결된 요소를 찾되 만약 연결된 요소 내에 사이클이 있으면 그 요소는 트리가 아니므로 트리 개수에서 제외시켜야 한다. 그러므로 이 문제의 핵심은 연결된 요소 내에서 사이클이 있는지를 판별하는 것이다. 그렇다면 어떻게 연결된 요소 내에 사이클이 있는지 판별할 수 있을까? 우선 연결된 요소를 파악하기 위해서는 그래프의 각 점에 대해 BFS나 DFS를 적용해야 한다. 특별히 트리에 DFS를 적용한다고 가정하자. 그러면 임의의 정점에서 시작해도 연결된 요..