DFS16 [C++] 백준 16724번: 피리 부는 사나이 (DFS) https://www.acmicpc.net/problem/16724문제 이해하기 문제의 요구사항은 다음과 같습니다.방향 지도가 주어질 때 회원들이 지도 어느 구역에 있더라도 SAFE ZONE에 들어가게 하는 SAFE ZONE의 최소 개수를 구하여라. 우선 직관적으로 문제를 살펴보면 SAFE ZONE의 위치는 이동이 순환되는 위치에 있음을 알 수 있습니다. 즉, 그래프에서 사이클이 형성되는 위치에 SAFE ZONE을 배치하면 해당 경로의 어느 위치에서 SAFE ZONE에 도달할 수 있습니다. 하지만, 항상 사이클이 생기지 않을 수도 있으니 이를 더 일반화해봅시다. 사이클이 형성되지 않더라도 같은 경로의 마지막 위치에 SAFE ZONE을 배치하면 해당 경로의 모든 위치는 마지막 SAFE ZONE으로 이동하게.. 2024. 10. 25. [C++] 백준 15681번: 트리와 쿼리 (DP) https://www.acmicpc.net/problem/15681문제 이해하기 문제의 요구사항은 다음과 같습니다.루트가 R인 트리가 주어질 때, 어떤 노드 U를 루트로 하는 서브트리에 속한 정점의 수를 구하여라.시간복잡도 어림하기DFS 알고리즘 서브트리의 개수를 구하는 문제이므로 DFS를 사용할 수 있습니다. 정점의 수가 N인 트리에서 DFS 알고리즘을 사용하면 O(N)의 시간복잡도를 가집니다. 한 번 방문한 정점은 다시 방문하지 않기 때문입니다. 이 과정을 모든 쿼리 Q번 반복하면 시간복잡도는 O(NQ) 입니다. N과 Q의 최댓값은 모두 100,000 이고, NQ = 100,000 x 100,000 = 10,000,000,000 (백억)이므로 제한 시간 내에 해결하기 어려운 수치입니다. 따라서 DFS.. 2024. 10. 15. [C++] 백준 1937번: 욕심쟁이 판다 (DP, DPS) https://www.acmicpc.net/problem/1937문제 이해하기 문제의 요구사항은 다음과 같습니다.판다가 항상 더 많은 대나무가 있는 위치로 이동할 때, 판다가 이동할 수 있는 최대 칸 수를 구하여라.시간복잡도 어림하기DFS 알고리즘 시작 위치에서 최대로 이동가능한 위치를 찾는 알고리즘으로 DFS를 사용할 수 있습니다. DFS는 O(N^2)의 시간복잡도가 필요합니다. 이 문제에서 시작 위치는 정해진 것이 없으므로 모든 위치에 대해 DFS를 사용해야합니다. 즉, 시간복잡도가 O(N^4)가 됩니다. 문제에서 N의 최댓값은 500이므로 이는 제한 시간 내에 해결하기 어려운 시간복잡도 입니다. 따라서 다른 알고리즘을 사용해야 합니다. DP 알고리즘 위 DFS 알고리즘의 동작을 다시 생각해 보면 중.. 2024. 8. 9. [C++] 백준 9466번: 텀 프로젝트 (DFS) https://www.acmicpc.net/problem/9466문제 이해하기 문제의 요구사항은 다음과 같습니다.선택의 결과를 보고 어느 프로젝트 팀에도 속하지 않는 학생들의 수를 계산해라. 문제 이해를 위해 아래 그림을 살펴봅시다. 그림을 보면 쉽게 알 수 있듯이, 그래프에서 사이클(Cycle)을 형성하는 노드들이 한 프로젝트 팀에 속하게 됩니다. 따라서 이번 문제는 사이클을 형성하는 노드의 수를 구하고, 전체 노드 수에서 뺀 결과를 구하면 되는 것입니다.시간복잡도 어림하기DFS 알고리즘 그래프 내에서 사이클을 찾기 위해서는 그래프를 탐색해야합니다. 그래프를 탐색하는 알고리즘으로 DFS 알고리즘을 사용할 수 있습니다. 이번 문제에서는 한 노드당 반드시 하나의 간선만 가지므로 DFS의 시간복잡도는 O(.. 2024. 7. 19. [C++] 백준 1520번: 내리막 길 (DP, DFS) https://www.acmicpc.net/problem/1520문제 이해하기 문제의 요구사항은 다음과 같습니다.주어진 지도를 바탕으로 제일 왼쪽 위 칸에서 제일 오른쪽 아래 칸으로 내리막길을 통해 이동하는 경로의 수를 구하여라. 시간복잡도 어림하기DFS 알고리즘 DFS를 사용하여 가능한 모든 경로를 탐색해 제일 오른쪽 아래에 도달하는 경로의 수를 구할 수 있습니다. 한 칸에서 다른 경로로 이동할 때, 이전 칸을 제외하고 3 방향으로 이동할 수 있습니다. 따라서 한 칸당 3가지의 경우의 수를 가집니다. 문제에서 N x M의 최댓값은 500 x 500 = 250,000이므로 가능한 경로의 수는 3 ^ 250000 개입니다. 이는 제한 시간 내에 문제를 해결할 수 없는 수치이므로 DFS 알고리즘을 사용할 .. 2024. 7. 17. [C++] 백준 1707번: 이분 그래프 (DFS) https://www.acmicpc.net/problem/1707문제 이해하기 문제의 요구사항은 다음과 같습니다.주어진 그래프가 이분 그래프인지 판별하라. 이분 그래프의 정의는 다음과 같습니다.그래프의 정점을 두 집합으로 분할했을 때, 각 집합의 정점끼리는 서로 인접하지 않는 그래프시간복잡도 어림하기DFS 알고리즘 우선 그래프 탐색을 해야 하는 문제이므로 DFS 알고리즘을 생각해 볼 수 있습니다. DFS 알고리즘의 시간복잡도는 인접리스트에서 O(V + E) 이고, 이 문제에서 V의 최댓값은 20,000, E의 최댓값은 200,000으로 제한 시간 내에 문제를 해결하기 충분한 수치입니다.알고리즘 설계하기 문제를 해결하기 위해 제가 생각한 방법은 두 가지가 있습니다. 첫 번째는 먼저 정점을 두 그룹으로 나.. 2024. 7. 1. 이전 1 2 3 다음
