BaekJoon 15681번 : 트리와 쿼리 (python)

BaekJoon 15681번 : 트리와 쿼리 (G5 45.339%)

트리와 쿼리 문제

DFS를 이용한 트리 탐색 + DP문제이다.

DFS 이용

• 주어진 루트 노드를 이용하여 DFS를 통해 리프노드까지 내려갔다가 올라오면서 해당 루트 노드의 개수를 업데이트 하는 방식을 이용한다.
• DFS를 통해 방문할 때 마다 방문여부를 확인해주고 만약 이미 방문한 노드라면 dp 업데이트를 하지 않고, 처음 방문한 노드라면 현재 dp값에 하위 노드들의 dp값을 담고 있는 DFS(i)로 업데이트 해준다.

BFS 이용

• 개인적으로 DFS보단 BFS가 더 편해서 BFS로도 풀 수 있지 않을까 라는 생각으로 시도를 해보았는데 BFS특징으로 너비 우선 탐색이기 때문에 탐색 순서가 루트 -> 리프노드 순으로 탐색이 된다.
• 이를 이용해 탐색 순서를 구하고 탐색 순서 역순으로 dp를 업데이트 해줌으로써 바텀 업 방식으로 DP를 업데이트 해줄 수 있게 된다.

---

DFS이용한 Bottom-Up방식

import sys
from collections import deque
input = sys.stdin.readline

def dfs(root) :
    if visit[root] :
        return dp[root]
    visit[root] = True

    for i in edges[root] :
        if visit[i] :
            continue
        dp[root] = dp[root] + dfs(i)
        
    return dp[root]

N, R, Q = map(int,input().split())
edges = [[]*(N+1) for _ in range(N+1)]
dp = [1]*(N+1)
visit = [False]*(N+1)
root = list(i for i in range(N+1))

for _ in range(N-1) :
    a, b = map(int,input().split())
    edges[a].append(b)
    edges[b].append(a)

dfs(R)
for _ in range(Q) :
    print(dp[int(input())])

---

BFS를 이용한 방법(리프노드 찾아서 Bottom-up 방식 이용)

import sys
from collections import deque
input = sys.stdin.readline

def bfs(R) :
    order = []
    q = deque([R])
    check = [False] * (N+1)
    check[R] = True
    while q :
        nx = q.popleft()
        order.append(nx)
        for i in edges[nx] :
            if not check[i] :
                check[i] = True
                root[i] = nx
                q.append(i)
    
    for node in order[::-1] :
        for neighbor in edges[node] :
            if neighbor != root[node] :
                dp[node] += dp[neighbor]

N, R, Q = map(int,input().split())
edges = [[]*(N+1) for _ in range(N+1)]
dp = [1]*(N+1)
visit = [False]*(N+1)
root = list(i for i in range(N+1))

for _ in range(N-1) :
    a, b = map(int,input().split())
    edges[a].append(b)
    edges[b].append(a)

bfs(R)
for _ in range(Q) :
    print(dp[int(input())])

---