백준_15957_음악추천(해결 못함)

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

15957번: 음악 추천

해결 방법

> 입력을 받아 트리를 그린다.

> 각 노드의 서브트리의 노드 개수를 구한다.(가중치를 나누기 위함)

> dfs를 돌면서 가중치를 적용시킨다.

> 트리를 순회하면서 가중치가 목표 점수에 도달하면 걸린시간을 체크한다.

 

결과

> 시간 초과

> 내가 생각한 이유 : 노드의 개수가 10만개인데 내가 짠 코드는 dfs를 10만번 돌고 또 돌아야 하기 떄문에 시간초과가 난 것 같다.

 

코드

import sys

from collections import defaultdict

 

sys.setrecursionlimit(10 ** 6)

 

def DFS_visit(adj, u, visited):

    if num_subnode[u] != None:

        return

    visited.append(u)

    for v in adj[u]:

        if v not in visited:

            DFS_visit(adj, v, visited)

 

def DFS(adj, s):

    visited =[]

    DFS_visit(adj, s, visited)

    num_subnode[s] = len(visited)

 

def DFS_visit_cal(adj, u, visited, time, w):

    visited.append(u)

    index = result[u - 1][2] - 1

    if not check[index]:

        result[u - 1][1] += w

        if (result[u - 1][1] // singer_count[result[u - 1][2]]) >= target_score:

            check[index] = True

            output[result[u - 1][2]] = time

    for v in adj[u]:

        if v not in visited:

            DFS_visit_cal(adj, v, visited, time, w)

 

def DFS_cal(adj, s, time, w):

    visited =[]

    DFS_visit_cal(adj, s, visited, time, w)

 

musictree = defaultdict(set)

num_music, num_data, target_score = map(int, input().split())

parent_node = list(map(int, input().split()))

parent_node.insert(0,0)

 

#가수 처리

singer = list(map(int, input().split()))

singer_count = defaultdict(int)

for i in singer:

    singer_count[i] += 1

 

for i in range(1, num_music + 1):

    for j in range(num_music):

        if parent_node[j] == i:

            musictree[i].add(j + 1)

 

num_subnode = list(None for i in range(num_music + 1))  #서브트리의 노드 개수

for i in range(1, num_music + 1):

    DFS(musictree,i)

 

result = list()

for i in range(num_music):

    result.append([0,0,singer[i]])    #시간, 가중치, 가수

 

check = [False for i in range(num_music)]

output = defaultdict(lambda: -1)

 

for i in range(num_music):

    time, subtree, weight = map(int, input().split())

    DFS_cal(musictree, subtree, time, weight//num_subnode[subtree])

 

for i in singer:

    print(output[i])