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

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

페이지 맨 위로 올라가기

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

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

[골드 5] 백준 15681 - 트리와 쿼리 (파이썬)

  • 2025.04.28 15:13
  • Programming/백준
글 작성자: pental

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

풀이

  • 루트가 R인 트리가 주어짐
  • 각 쿼리는 정점 U를 루트로 하는 서브트리의 정점 개수를 묻는다
  • 여러 쿼리에 대해 빠르게 답변해야 하므로 DFS를 활용한 서브트리 크기 미리 계산이 핵심
adj = [[] for _ in range(N)]

adj[u]에 연결된 정점들 v를 저장하여 무방향 트리를 구성한다.

D = [0] * N

D[u]는 u를 루트로 하는 서브트리의 정점 수를 나타낸다.

def dfs(u):
    visit[u] = True
    D[u] = 1  # 자기 자신 포함

    for v in adj[u]:
        if not visit[v]:
            dfs(v)
            D[u] += D[v]

DFS를 통한 서브트리 크기를 계산하며, 재귀적으로 자식 노드의 서브트리 크기를 더해준다.

한번의 DFS로 모든 정점의 서브트리 크기 계산이 가능하다.

for _ in range(Q):
    u = int(input())
    u -= 1
    print(D[u])

이미 계산해둔 D[u] 값을 출력하면 되므로 O(1) 시간을 가진다.

코드

# 백준 15681 - 트리와 쿼리
# 분류 : 다이나믹 프로그래밍

import sys
sys.setrecursionlimit(100000000)
input = sys.stdin.readline

N, R, Q = map(int, input().split())
R -= 1
adj = [[] for _ in range(N)]

for _ in range(N - 1) :
    u, v = map(int, input().split())
    u -= 1
    v -= 1

    adj[u].append(v)
    adj[v].append(u)

visit = [False] * N
D = [0] * N

def dfs(u) :
    visit[u] = True
    D[u] = 1

    for v in adj[u] :
        if not visit[v] :
            dfs(v)
            D[u] += D[v]

dfs(R)

for _ in range(Q) :
    u = int(input())
    u -= 1

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

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

[골드 2] 백준 2637 - 장난감 조립 (파이썬)  (0) 2025.04.28
[골드 5] 백준 12865 - 평범한 배낭 (파이썬)  (1) 2025.04.28
[실버 2] 백준 11060 - 점프 점프 (파이썬)  (0) 2025.04.27
[실버 3] 백준 9657 - 돌 게임 3 (파이썬)  (0) 2025.04.27
[골드 2] 백준 1655 - 가운데를 말해요 (파이썬)  (0) 2025.04.26

댓글

이 글 공유하기

  • 구독하기

    구독하기

  • 카카오톡

    카카오톡

  • 라인

    라인

  • 트위터

    트위터

  • Facebook

    Facebook

  • 카카오스토리

    카카오스토리

  • 밴드

    밴드

  • 네이버 블로그

    네이버 블로그

  • Pocket

    Pocket

  • Evernote

    Evernote

다른 글

  • [골드 2] 백준 2637 - 장난감 조립 (파이썬)

    [골드 2] 백준 2637 - 장난감 조립 (파이썬)

    2025.04.28
  • [골드 5] 백준 12865 - 평범한 배낭 (파이썬)

    [골드 5] 백준 12865 - 평범한 배낭 (파이썬)

    2025.04.28
  • [실버 2] 백준 11060 - 점프 점프 (파이썬)

    [실버 2] 백준 11060 - 점프 점프 (파이썬)

    2025.04.27
  • [실버 3] 백준 9657 - 돌 게임 3 (파이썬)

    [실버 3] 백준 9657 - 돌 게임 3 (파이썬)

    2025.04.27
다른 글 더 둘러보기

정보

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

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

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

검색

메뉴

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

카테고리

  • Category (452) N
    • Forensics (105)
      • Magnet AXIOM (28)
      • Digital Forensics Informati.. (9)
      • Iphone Forensics (24)
      • 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 (260) N
      • C (10)
      • Python (11)
      • 백준 (206) 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.

티스토리툴바