문제
입력
첫째 줄에 직원의 수 N이 주어진다. 둘째 줄에는 0번 직원부터 그들의 상사의 번호가 주어진다. 0번 직원 (오민식)은 상사가 없기 때문에 -1이고, 나머지 직원 i의 상사 번호는 i보다 작거나 같은 음이 아닌 정수이다. N은 50보다 작거나 같은 자연수이다.
출력
첫째 줄에 모든 소식을 전하는데 걸리는 시간의 최솟값을 출력한다.
❗ 풀이
문제 접근 1
문제에서 대놓고 트리 구조인 것을 알려주었고, 자식 노드에서 걸린 시간이 부모 노드에게 영향이 가기 때문에, 다이나믹 프로그래밍을 활용하여 풀고자 했다. DP를 사용하는 것은 쉽지만 문제는 트리구조에서 어떻게 활용할지 였는데, 자식 노드가 여러 개일 경우, 자식 노드들이 가지고 있는 자식 노드의 개수로 내림차순 정렬하여 앞에서부터 전화를 돌리는 알고리즘으로 코드를 짰다.
코드 1
# 뉴스 전하기
'''
자식의 수가 많은 노드부터 전화걸기
'''
N = int(input()) # 사원 수
arr = list(map(int, input().split())) # 부모 노드 입력
tree = [[]for _ in range(N)] # 트리를 위한 2차원 리스트
for i in range(1,N):
tree[arr[i]].append(i) # 부모 노드에 넣기
dp = [0]*(N) # dp를 위한 리스트 선언
def treedp(x):
chi_num = [(len(tree[i]),i) for i in tree[x]] # (자식노드의 자식 개수, 자식 노드 번호) 저장, 내림차순으로 정렬
chi_num.sort(reverse=True)
std = dp[x] # 부모 노드의 dp값
for child, num in chi_num: # 정렬한 순서대로 전화하기
std += 1 # 순서대로 1씩 증가
dp[num] = std # 부모노드 dp값 + 순서가 자신에게 전화 걸려온 시간
if child: # 자식이 있을 경우 재귀함수 호출
treedp(num)
treedp(0)
print(max(dp))
결과는 1%에서 바로 틀리고 말았다. 이유가 무엇인지 아무리 생각해도 떠오르지 않아서, 여러 트리를 직접 그려보고 드디어 해답을 얻을 수 있었다.
문제 접근 2
자식의 개수로만 접근했을 경우, 바로 한단계 하위 문제만 고려하고 더 밑에 있는 하위 문제들은 무시해버리는 것을 깨달았다. 즉, DP인 것을 알면서도 DP처럼 문제를 접근하지 못했던 것이다.
트리를 여러 번 그리고 바텀업 방식으로 값을 계산해나가면서 현재 노드의 소요 시간을 산출하는데에 그리디 알고리즘도 적용시켜야 하는 것을 알아낼 수 있었다. 일단 자식을 걸리는 시간으로 내림차순 정렬한 다음, (순서 + 걸리는 시간) 값을 각 자식 별로 구한다. 이 값들 중 가장 큰 값이 부모 노드의 비용이 된다. 점화식으로 표현하면 다음과 같다.
a = max(list(각 순서 +각 비용))
(여기서 child_list는 자식 노드의 걸리는 시간들을 내림차순으로 정렬한 리스트이다)
코드 2
N = int(input())
arr = list(map(int, input().split()))
tree = [[]for _ in range(N)]
for i in range(1,N):
tree[arr[i]].append(i)
dp = [0]*(N)
# 여기까진 첫 코드와 동일
def treedp(x):
if tree[x]:
under_tree = sorted([treedp(i) for i in tree[x]], reverse=True) # 자식 노드의 비용을 내림차순으로 정렬
dp[x] = max([i+1+under_tree[i] for i in range(0, len(tree[x]))]) # 정렬된 순서 + 비용 값 중 가장 큰 값이 부모 노드의 비용
else:
return dp[x] # 자식 노드가 없을 경우 현재 노드의 비용 반환
return dp[x] # 모두 계산이 끝났을 경우 노드의 비용 반환
treedp(0) # 가장 꼭대기부터 출발
print(max(dp))
결과는 바로 통과. 알고리즘을 구현해놓고도 코드의 볼륨이 너무 작아서 뭔가 더 놓친게 있을 것 같은 느낌이 들었지만, 트리를 여러번 그려서 얻은 인사이트가 적확했다.
정리
이 문제는 특이하게 트리라는 자료구조를 정해주는 문제였는데 이 점이 DP로 접근할 수 있는 가장 큰 힌트임에도 불구하고 놓친 것이 너무 아쉬웠다. 문제가 DP임을 알았을 때 전체 문제를 작은 문제 단위로 쪼개면서 이게 끝까지 쪼개진 단위인지 확실하게 확인하는 절차를 가지는 것이 중요할 것 같다.
