ndb796
p531 복잡도에 관해 질문있습니다.
p531 연구소 문제 풀이에서 복잡도에 관해 질문이 있습니다. 64C3이 100,000보다도 작은 수이므로, 모든 경우의 수를 고려해도 제한 시간 안에 해결할 수 있다고 설명이 되어있는데 조금 더 자세한 설명을 해주실 수 있으신가 하여 질문드립니다. 문제 풀이에서 사용되는 알고리즘이 DFS 즉, 시간 복잡도가 선형시간이므로 범위 N이 100,000 이어도 풀이가 가능하다는 뜻인가요??
안녕하세요, @backtony 님!
문제 해설에 명시되어 있듯이 모든 조합의 개수는 64C3 이므로, 100,000보다 작습니다. (N = 8이라고 가정) 조합마다 BFS를 이용하여 안전 영역의 크기를 구하면 됩니다.
이때 DFS나 BFS를 이용한 탐색 알고리즘의 경우 전체 탐색 공간이 시간 복잡도와 비례합니다. 따라서 조합마다 탐색 공간의 크기가 8 X 8 = 64까지 될 수 있으므로 (간선을 무시할 때) 전체 연산 횟수는 100,000 X 64 = 6,400,000 이하가 될 것으로 기대할 수 있습니다.
이 문제는 N의 범위가 최대 8 이하로 매우 한정적이기 때문에 완전 탐색으로 해결이 가능하다고 보시면 됩니다. 엄밀한 계산은 아니지만, 연산 횟수는 (N^2)C3 * (N^2) 정도로 볼 수 있을 것입니다. 다시 말해 선형 시간보다 훨씬 복잡도가 높습니다. N = 100,000인 경우에 이 문제를 동일 알고리즘으로 푸는 것은 비현실적인 시간을 요구할 것입니다.
감사합니다. 나동빈 드림
