백준 1135 뉴스 전하기 파이썬 풀이

난이도 : 골드2

풀이일 : 2403251

https://www.acmicpc.net/problem/1135

1135번: 뉴스 전하기

---

링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐

---

풀이코드

import sys


def dp(n):
    # 이전에 검사한 적이 있다면 검사 결과 반환 종료
    if time[n] > -1:
        return time[n]

    # 해당 노드의 자식이 없다면 0 저장 후 0 반환 종료
    if not children[n]:
        time[n] = 0
        return 0

    # 모든 자식 노드 방문 소요 시간 계산
    temp = [dp(child) for child in children[n]]

    if temp:  # 자식노드가 있다면 내림차순 정렬
        temp.sort(reverse=True)

        # 방문 순서에 따른 추가 시간 반영
        for idx, t in enumerate(temp):
            temp[idx] = idx + t

        # temp 최고값에 현재 노드 방문 시간 반영
        time[n] = max(temp) + 1
        return time[n]


N = int(sys.stdin.readline())
parent = list(map(int, sys.stdin.readline().split()))
children = [[] for _ in range(N)]  # 자식 정보 배열
time = [-1] * N  # 누적시간 저장

# 자식 정보 저장
for i in range(N):
    if parent[i] >= 0:
        children[parent[i]].append(i)

# 시간 탐색
for i in range(N):
    dp(i)

# 루트 노드의 시간 출력
print(time[0])

• 자식을 가지지 않는 가장 깊은 깊이의 노드부터 dp 탐색을 진행하고, dp 결과들을 모아 최종 값을 도출해내는 방식
• 이전에 조사하였는지 여부를 확인하기 위해 time의 초기값 -1 설정
• 자식을 가지지 않는 노드는 time[n]에 0 저장
• 자식을 가지고 있는 노드는 누적 자식 방문의 최고값에 현재 노드 방문 시간(+1)을 합산하여 time[n] 저장
• enumerate : 인덱스와 항목을 튜플 형식으로 반환하는 자료형. 각 항목에 인덱스를 합산해주기 위해 사용
• 모든 노드 방문 시간 계산 후, 루트노드 [0]의 시간 time[0] 출력

---

느낀점

• enumerate는 알고리즘에서 처음 써본 것 같다. 처음에는 for문으로 인덱스를 직접 더하다가, 조금 더 간단하게 풀이할 방법이 있을 것 같아 찾아보고 적용했다. 파이썬이 제일 익숙한데도 이렇게 안써본 자료형이 넘쳐나다니... 알고리즘을 풀 때 다양하게 시도해보고, 파이썬에 충분히 적응할 수 있도록 노력하자
• 또, 예전에 여러 번 틀렸던 문제라서 맞췄을 때 훨씬 기분이 좋았다. 알고리즘 폴더에 남아있는 못 풀었던 문제들을 하나씩 검색해보며 푼 문제 파일은 삭제하고, 못 풀어낸 문제들을 따로 정리하였는데, 오늘처럼 못 푼 문제 중에 하나씩 골라 해결해야지