문제 설명
숫자 리스트 nums가 주어진다고 가정해 보겠습니다. 이때 nums[i]는 i번째 동물의 포식자(잡아먹는 동물)를 나타내며, 포식자가 없으면 -1이 저장됩니다. 우리가 구해야 할 것은 어떤 동물도 자신의 직접적 또는 간접적 포식자와 같은 그룹에 속하지 않도록 동물들을 나눌 때 필요한 그룹 수의 최솟값입니다.
예를 들어 입력이 nums = [1, 2, -1, 4, 5, -1]라면 출력은 3입니다. 그룹을 [0, 3], [1, 4], [2, 5] 형태로 구성할 수 있기 때문입니다.
핵심 아이디어
0번 동물은 1번에게, 1번 동물은 2번에게 잡아먹히므로 하나의 포식자 사슬(0 → 1 → 2)을 이룹니다. 같은 사슬 위에 있는 동물들은 반드시 서로 다른 그룹에 배정되어야 하므로, 필요한 최소 그룹 수는 가장 긴 포식자 사슬의 길이와 같습니다. 따라서 이 문제는 포식자가 없는 동물(루트)에서 시작해 사슬의 최대 깊이를 구하는 그래프 탐색 문제로 바꿔 해결할 수 있습니다.
풀이 절차
- 리스트 A가 비어 있으면 0을 반환합니다.
- 인접 리스트(adj), 방문 집합(vis), 루트 목록(roots)을 준비합니다.
- A를 순회하면서 값이 -1인 인덱스는 루트로 기록하고, 각 쌍 (i, a)에 대해 adj[i]와 adj[a]에 서로를 추가해 무방향 그래프를 만듭니다.
- best를 음의 무한대로 초기화합니다.
- 각 루트에서 스택 기반 DFS를 수행하며 깊이(d)를 추적하고, best를 지금까지 발견한 최대 깊이로 갱신합니다.
- best를 반환합니다.
예제 코드
from collections import defaultdict
class Solution:
def solve(self, A):
if not A:
return 0
adj = defaultdict(list)
vis = set()
roots = []
for i, a in enumerate(A):
if a == -1:
roots.append(i)
adj[i].append(a)
adj[a].append(i)
best = -float("inf")
for root in roots:
stk = [(root, 1)]
while stk:
node, d = stk.pop()
if node in vis or node == -1:
continue
best = max(best, d)
vis.add(node)
for u in adj[node]:
stk.append((u, d + 1))
return best
ob = Solution()
nums = [1, 2, -1, 4, 5, -1]
print(ob.solve(nums))
입력
[1, 2, -1, 4, 5, -1]
출력
3
동작 원리 살펴보기
위 예제에서 2번과 5번 동물은 포식자가 없으므로 루트입니다. 각 루트에서 탐색을 시작하면 2 → 1 → 0, 5 → 4 → 3이라는 두 개의 포식자 사슬이 발견되며, 각 사슬의 깊이는 3입니다. 따라서 best는 3으로 갱신되고, 이 값이 곧 필요한 최소 그룹 수가 됩니다.
이 풀이는 모든 노드를 한 번씩만 방문하므로 시간 복잡도는 O(N)이며, 공간 복잡도 역시 O(N)으로 효율적입니다.