이 영역을 누르면 첫 페이지로 이동
포렌식 & 개발 이야기 - Forensics & Development 블로그의 첫 페이지로 이동

포렌식 & 개발 이야기 - Forensics & Development

페이지 맨 위로 올라가기

포렌식 & 개발 이야기 - Forensics & Development

Pental - Forensics / iOS / Windows / Android / Kakaotalk / Telegram / Etc

[골드 2] 백준 1135 - 뉴스 전하기 (파이썬)

  • 2025.04.19 15:28
  • Programming/백준
글 작성자: pental

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

풀이

  • 회사에는 N명의 직원이 있고, 0번 직원이 사장이다.
  • 각 직원은 한 명의 상사를 가지고 있다. (par[i]가 i번 직원의 상사)
  • 뉴스는 각 사장(0번)부터 시작해서 전파되며, 각 직원은 동시에 한명에게만 뉴스 전달을 시작할 수 있다.
  • 모든 직원이 뉴스를 전달받기까지 걸리는 최소 시간을 구하는 문제이다.

문제는 트리 형태의 구조에서, 루트 노드로부터 모든 노드에게 최대한 빠르게 뉴스를 전파하는 방식으로 시간을 최소화하는 것이다.

서브트리들 간의 전파 순서에 따라 시간 차이가 발생하므로, 더 오래 걸리는 자식부터 먼저 처리하는 것이 유리하다.

child = [[] for _ in range(N)]
for i in range(1, N):
    child[par[i]].append(i)
  • child[u]는 u번 직원의 부하들 리스트이다.
  • 루트(0번 사장)을 기준으로 하위 트리 구조를 만든다.
D = [0] * N

def dfs(u):
    times = []
    for v in child[u]:
        dfs(v)
        times.append(D[v])
    
    times.sort(reverse=True)

    D[u] = 0
    for i in range(len(times)):
        D[u] = max(D[u], i + 1 + times[i])
  • 이 문제는 DFS + DP로 해결이 가능하다.
  • D[u]는 u번 노드가 자신의 모든 부하 직원들에게 뉴스를 전하는데 걸리는 최소 시간이다.
  • 자식 노드들을 몰면서 D[v]값을 모은다.
  • 시간이 오래 걸리는 자식에게 먼저 뉴스를 전달하면 전체 시간이 최소화된다.

예를 들어서 입력과 구조에 대해서 작성한다.

4
-1 0 0 1

이런 입력이 있을 때 트리의 구조는 다음과 같다.

     0
    / \\
   1   2
  /
 3
  • 전파 순서를 확인하면,
    • 0번에서 1, 2에는 동시에 전파된다.
    • 1번에서 3에 전파한다.
  • 각 시간을 확인하면
    • 0번에서, 1, 2에는 1초
    • 1번에서 3에는 1초
    • 총 2초가 사용된다.

코드

# 백준 1135 - 뉴스 전하기
# 분류 : 다이나믹 프로그래밍

N = int(input())
par = list(map(int, input().split()))

child = [[] for _ in range(N)]
for i in range(1, N) :
    child[par[i]].append(i)

D = [0] * N

def dfs(u) :
    # D[u] 의 값을 구하는게 최종 목표

    times = []
    for v in child[u] :
        dfs(v)
        times.append(D[v])
    
    times.sort(reverse=True)

    D[u] = 0
    for i in range(len(times)) :
        D[u] = max(D[u], i + 1 + times[i])

dfs(0)
print(D[0])
저작자표시 비영리 (새창열림)

'Programming > 백준' 카테고리의 다른 글

[실버 3] 백준 3273 - 두 수의 합 (파이썬)  (0) 2025.04.20
[골드 3] 백준 2616 - 소형기관차 (파이썬)  (0) 2025.04.20
[브론즈 1] 백준 1333 - 부재중 전화 (파이썬)  (1) 2025.04.19
[실버 3] 백준 8911 - 거북이 (파이썬)  (0) 2025.04.19
[골드 5] 백준 13549 - 숨바꼭질 3 (파이썬)  (1) 2025.04.18

댓글

이 글 공유하기

  • 구독하기

    구독하기

  • 카카오톡

    카카오톡

  • 라인

    라인

  • 트위터

    트위터

  • Facebook

    Facebook

  • 카카오스토리

    카카오스토리

  • 밴드

    밴드

  • 네이버 블로그

    네이버 블로그

  • Pocket

    Pocket

  • Evernote

    Evernote

다른 글

  • [실버 3] 백준 3273 - 두 수의 합 (파이썬)

    [실버 3] 백준 3273 - 두 수의 합 (파이썬)

    2025.04.20
  • [골드 3] 백준 2616 - 소형기관차 (파이썬)

    [골드 3] 백준 2616 - 소형기관차 (파이썬)

    2025.04.20
  • [브론즈 1] 백준 1333 - 부재중 전화 (파이썬)

    [브론즈 1] 백준 1333 - 부재중 전화 (파이썬)

    2025.04.19
  • [실버 3] 백준 8911 - 거북이 (파이썬)

    [실버 3] 백준 8911 - 거북이 (파이썬)

    2025.04.19
다른 글 더 둘러보기

정보

포렌식 & 개발 이야기 - Forensics & Development 블로그의 첫 페이지로 이동

포렌식 & 개발 이야기 - Forensics & Development

  • 포렌식 & 개발 이야기 - Forensics & Development의 첫 페이지로 이동

검색

메뉴

  • 홈
  • 태그
  • 미디어로그
  • 위치로그
  • 방명록

카테고리

  • Category (450) N
    • Forensics (105) N
      • Magnet AXIOM (28)
      • Digital Forensics Informati.. (9)
      • Iphone Forensics (24) N
      • DFC (7)
      • 디지털포렌식전문가2급 자격증 (10)
      • FTK ACE 자격증 (7)
    • 이것저것 (7)
      • Ubuntu (6)
      • 디스코드 봇 (4)
      • Volatility GUI (2)
    • CTF (32)
      • NEWSECU (14)
      • CTF-d (5)
      • Puzzel - Network Forensics (2)
      • Security Traps (2)
      • system32.kr (5)
      • HMCTF (4)
    • Programming (258) N
      • C (10)
      • Python (11)
      • 백준 (204) N
      • 프로그래머스 (32)
    • 그냥 개발 및 잡담 (16)
      • Docker (2)
      • Google Cloud (3)
      • OS 개발 (3)
    • Best of Best (20)

최근 글

인기 글

댓글

공지사항

아카이브

태그

  • axiom
  • 백준
  • Forensics
  • 포렌식
  • 디지털포렌식
  • 파이썬
  • pental
  • 프로그래머스
  • 전체 보기…

정보

pental의 포렌식 & 개발 이야기 - Forensics & Development

포렌식 & 개발 이야기 - Forensics & Development

pental

블로그 구독하기

  • 구독하기
  • RSS 피드

방문자

  • 전체 방문자
  • 오늘
  • 어제

티스토리

  • 티스토리 홈
  • 이 블로그 관리하기
  • 글쓰기
Powered by Tistory / Kakao. Copyright © pental.

티스토리툴바