devbelly

문제 https://www.acmicpc.net/problem/7045 알고리즘 DFS 풀이 각 정점을 루트로 했을 때, 서브트리 크기의 최댓값이 절반 이하가 되는 정점을 찾는 문제입니다. 문제에서 주어진 $N$ 제한은 1만이므로 각 정점마다 DFS를 돌리면 $O(N^2)$ 이므로 시간초과를 받게 됩니다. 한 정점에서 DFS를 시작하여 임의의 정점에 도달했을 때, 해당 정점의 서브트리의 크기는 재귀적으로 찾을 수 있습니다. 추가적으로 고려해야할 것은 현재까지 탐색한 트리의 크기입니다. 이 정보는 현재까지 탐색했던 트리를 제외한 서브트리 크기의 총합을 안다면 $N-sum[i]$를 통해 구할 수 있습니다. $sum[i]$는 서브트리크기의 총합을 의미합니다. DFS를 수행한 후 각 정점마다 $MAX[i]$ 값..

문제 https://www.acmicpc.net/problem/18785 알고리즘 DFS 풀이 Bessie가 트리위에 주어진 맵을 이동해가며 시계를 조정할 때, 모든 시계가 가르키는 시간이 12시가 되도록 할수 있는 방의 시작갯수를 구하는 문제입니다. 임의의 출발지에서 모든 노드가 12가 될 수 있는지를 확인하는 것이 목표입니다. $N$제한이 2500이므로 $O(N^2)$에 근접하는 알고리즘을 떠올려봅시다. 첫 번째로는 리프노드의 시간을 12시로 맞추기 위해서는 무조건 리프노드와 리프노드의 부모를 계속해서 왔다갔다 해야지만 리프노드를 원하는 숫자 12로 맞출 수 있습니다. 12로 설정된 리프노드는 우리의 관심사 밖이므로 제거되고 리프노드의 부모였던 노드는 새로운 리프노드가 됩니다. 위 시뮬레이션을 계속 ..

문제 www.acmicpc.net/problem/17493 알고리즘 DFS 풀이 포레스트에서 트리의 지배집합의 수를 찾는 문제입니다. 동아리의 홍보효과가 인접한 지역까지 영향을 미칩니다. 하나의 트리에서 문제를 살펴보겠습니다. 잘 생각해보면 리프노드에는 굳이 홍보를 할 이유가 없습니다. 리프노드에 홍보를 하면 자신의 부모노드에만 영향을 미치지만 그 부모노드에 홍보를 하게 되면 리프노드뿐만 아니라 그 부모가 갖는 자식들에게 모두 홍보를 할 수 있기 때문입니다. 즉 리프노드의 부모노드는 무조건 홍보를 해야 이득임을 알 수 있습니다. [잘못된 풀이] 처음에 이 문제를 리프노드의 부모로부터 BFS를 수행해 현재 노드가 빨간 노드(홍보노드)면 주변은 노 란노드(영향을 받는 노드), 현재 노드가 노란 노드면 주변을..

문제 www.acmicpc.net/problem/16964 알고리즘 DFS 풀이 그래프와 방문 순서가 주어질 때, 올바른지 확인하는 문제입니다. 그래프는 2차원 벡터로 표현이 가능합니다. 문제에서 입력을 받는 순서로 그래프를 만들어 방문하는 대신, 방문 순서를 기준으로 그래프를 정렬합니다. 이후 루트 노드에서 DFS를 수행하면 방문 순서가 빠른 노드부터 방문하게 되므로 해당 방문 순서가 올바른 순서인지 파악할 수 있습니다. 이를 위해 $rev$배열을 만들어 방문 순서가 빠른 노드로 그래프를 정렬하도록 했습니다. 코드 #include #define rep(i, n) for (int i = 0; i u >> v; --u, ..

문제 www.acmicpc.net/problem/20647 알고리즘 DFS 풀이 $N$개의 목장이 트리 형태로 주어집니다. 1번 목장에 감염된 소가 있을 때, 모든 목장의 소가 감염되기 까지 최소일수를 구하는 문제입니다. 그리디 문제인데 자세한 관찰을 하지 못해 많이 틀렸습니다. 제 잘못된 관찰은 1번 목장에서 거리가 2이하인 목장들은 1번 목장에서 감염 후 이동해야한다고 생각했습니다. 이렇게 해야 복제시간에서 이득을 본다고 생각했기 때문입니다. (거리가 1인 노드를 무시한 채 거리가 2인 노드들만 고려해서 계산했음. [복제(1번노드)-이동-이동] 과 [복제(1번노드)-이동-복제(2번노드)-복제] 로 비교를 했지만 이는 거리가 1인 노드들을 처리하며 갈 수 있음을 무시한 계산이므로 틀렸음) 올바른 해는 ..

문제 www.acmicpc.net/problem/15591 알고리즘 DFS 풀이 $N$개의 정점이 트리를 이루고 각 엣지마다 가중치가 있을 때, 가중치가 $k$이상으로 이어져 있는 노드의 수를 구하는 문제입니다. $N$과 $Q$의 수가 최대 5000이므로 각 쿼리마다 $dfs$를 수행해도 시간초과가 나지 않습니다. $dfs(here, parent, weight)$를 호출하여 인접한 노드가 가중치 $k$이상으로 이어져 있는지 확인하면 됩니다. 코드 #include #define rep(i, n) for (int i = 0; i < n; ++i) #define REP(i, n) for (int i = 1; i = k && there != prv) { ret += 1; ret += dfs(there, here..

문제 www.acmicpc.net/problem/16768 알고리즘 dfs 풀이 인접한 곳에 동일한 숫자가 있으면 연결이 됩니다. 연결된 크기가 $K$이상일 때 숫자들은 터지고 터지는 숫자들이 없을 때까지 시뮬레이션 하여 결과를 출력하면 됩니다. 이 문제와 거의 유사한 문제로 조건이 4개가 모이면 터지는 것에서 $K$개가 모이면 터지는 것 외엔 다른 것이 없습니다. 연결된 크기를 세기 위한 $dfs$함수와 터지고나서 숫자들을 떨어뜨리는 $gravity$함수만 잘 구현하면 쉽게 풀 수 있습니다. 코드 #include #define rep(i, n) for (int i = 0; i N >> K; rep(i, N) rep(j..

문제 https://www.acmicpc.net/problem/17228 알고리즘 라빈 카프 해설 정원의 쉼터가$N-1$개의 길로 연결되어있다는 점에서 트리임을 알 수 있고, 반대방향으로 이동하는 것을 금지한다는 조건에서 DFS접근방식을 생각했습니다. 만영이 취향의 문자열을 해싱한 후, DFS를 수행하며 수행과정에서 얻는 문자열 또한 해싱하며, 해시값이 동일하다면 정답을 카운트해주면 됩니다. 처음 $recur()$ 에서는 롤링 해시할 길이가 없으므로, 가짜 문자인 $를 넣어주었습니다. DFS와 라빈 카프를 이용했으므로 시간 복잡도는 $O(V+E+N)$입니다. 코드 #include #include #define rep(i,n) for(int i=0;i N; adj.resize(N); rep(i, N - 1..