[CF 1118F1] Tree Cutting (Easy Version) - 1800 문제 설명 : 빨간색,파란색,무색(색깔 없음)노드로 이루어진 트리가 주어진다. 트리의 간선 (n-1)개 중에서 어느 한 간선을 제거했을 때 만들어지는 2개의 component가 있을텐데, 각 component를 이루는 노드의 색깔이 빨간색과 파란색이 동시에 존재하지 않도록 하는 간선이 몇 개인지 구하는 문제이다. 풀이 : 처음 생각한 것은 각 간선별로 하나씩 지워보고 만들어지는 2개의 component의 노드 색깔을 조사해볼까 생각해봤는데, 노드 수(간선 수)가 최대 30만이므로 이 풀이로는 힘들 것 같았다. 그래서 어떻게든 한 번의 순회만으로 제거할 수 있는 간선을 찾는 것이 유력하다고 생각했다. 정답을 만족시키는 두 ..
[Codeforces 954D] Fight Against Traffic - 1600 문제 설명 : 그래프에서 이미 길이 설치되어 있지 않은 두 노드 사이에 길을 추가했을 때, s에서 t로가는 최단거리의 값에 변함이 없도록 만드는 두 노드를 고르는 경우의 수를 구하는 문제이다. 풀이 : 전처리로써 처음에 모든 노드에서 s까지의 거리, 모든 노드에서 t까지의 거리를 모두 구해놓는다. a에서 b로 가는 도로가 생긴다는 의미는 곧 a->b 최단거리가 1이 됨을 의미한다. 따라서 s->a거리, b->t 거리만 추가로 더해주기만 하면(역도 고려해야 하긴 하지만) 'a,b 노드에 길을 추가함으로써 최종 s->t로 가는 최단거리'를 구할 수 있다. 그래서 새롭게 구한 최단거리가 원래의 최단거리보다 더 짧아졌는지 그대로..
[Codeforces 1006E] Military Problem - 1600 문제 설명 : 군대의 위계를 나타내는 트리가 주어지고, 쿼리가 주어진다. 각 쿼리는 두 개의 정수 u,k로 이루어져 있는데 쿼리마다 노드 u부터 시작해서 k번째로 방문하는 노드가 몇 번인지를 찾는 문제이다. 방문하는 원칙에는 반드시 현재 노드보다 위계가 낮은(아래)노드로만 방문이 가능하며, 자식이 여럿일 때는 노드 번호가 작은 순부터 방문한다. 풀이 : 트리의 노드가 최대 20만개, 쿼리도 최대 20만개이므로 매 쿼리를 계산할 때 최대 O(logN)이내에 수행해야 한다. 따라서 전처리 단계부터 쿼리에 빠르게 답할 수 있도록 처리해야 한다. 그러기 위해서 나는 두 개의 배열을 마련할 것이다. 하나는 (밑의 소스코드와 같이) cnt..
[Codeforces 1084D] The Fair Nut and the Best Path 문제 설명 : n개의 노드가 있는 트리가 있다. 각 노드에는 양의 가중치가 있으며, 노드 간의 간선에도 가중치가 있다. 노드를 지날 때는 그 노드에 배정된 가중치 만큼 값을 더할 수 있으며, 간선을 지날 때에는 그 간선에 배정된 가중치 만큼 가중치가 차감된다. 이때 얻을 수 있는 최대의 가중치의 합을 구하는 문제이다. 각 노드는 단 한번만 방문이 가능하며, 시작 지점은 어디든 상관없다. 풀이 : 이 문제에서의 가장 중요한 이슈는 트리를 순회하면서 앞으로 갈 노드(next)를 방문하는 것이 이득일지 아닐지에 대한 문제이다. 이를 구하는 함수가 dfs(next)인데, 이 dfs(next)의 반환값이 양수라면 방문하는 것..
[Codeforces 1082D] Maximum Diameter Graph 문제 설명 : n개의 vertex에 대해서 각 vertex당 최대로 연결 가능한 degree의 수가 주어진다. 그 degree 이내에서 만들 수 있는 그래프 중에서 지름의 길이가 가장 길도록 그래프를 만들 때, 지름의 길이와 그 때의 간선 연결 관계를 출력하는 문제이다. 풀이 : 이 문제에서 가장 먼저 생각해야 할 점은 '지름의 길이를 최대가 되도록'해야한다. 어떻게 하면 최대가 될까? 일단 그래프를 반드시 트리의 형태로 만들어야 한다. 사이클이 생기는 그래프는 지름의 길이가 짧아질 수도 있다. 트리로 만들겠다고 방향을 잡은 뒤에 생각할 것은 vertex들을 어떻게 연결해야 지름이 가장 길어질 것인가에 대한 생각이다. degree..
[Codeforces 1144F] Graph Without Long Directed Paths Problem - F - Codeforces codeforces.com 유형 : DFS, graph 문제 설명 : 입력으로 vertex가 n개이고 u와 v를 연결하는 undirectd인 간선이 m개 주어진다. 이 간선들을 directed로 전환해서 그래프에 길이가 2이상인 경로가 없도록 만들어야 한다. 어떻게 전환해도 불가능한 경우에는 "NO"를 출력하고, 가능하다면 "YES"와 함께 입력에서 주어진 간선의 정보 (u->v)를 그대로 전환한다면 0을 출력하고, 그와 반대인 (v->u)로 전환한다면 1을 출력하는 문제이다. 풀이 : 예전에 푼 적이 있는 [Codeforces 1093D] Beautiful Grap..
[Codeforces 1093D] Beautiful graph 그래프 문제를 풀 때는 항상 Disjoint된 상태를 고려해야한다는 교훈을 일깨워준 문제. 그래프의 vertex에 1,2,3중에 하나의 숫자를 부여해야 하는데, edge로 연결된 두 vertex끼리는 두 수의 합이 반드시 홀수가 되게 만들어야 한다. 이 조건을 만족하게 숫자를 부여하는 방법의 경우의 수를 구하는 문제이다.내가 우선 생각한 것은 두 수를 더해서 홀수가 되도록 만드는 방법이었다. 두 수를 더해서 홀수가 되게 하려면 (짝수+홀수) 의 방법밖에 존재하지 않는다. 이 문제에서 사용할 수 있는 짝수는 2밖에 없고, 홀수는 1,3밖에 없다. 그래서 나는 그래프를 구성한 뒤 dfs를 돌면서 각 노드마다 번갈아가면서 홀->짝->홀->짝... ..