[파이썬] 백준 1005 : ACM Craft (골드3)

[파이썬] 백준 1005 : ACM Craft (골드3)

 

1005번: ACM Craft

---

문제

---

풀이

0. 방향성 생각

하위 노드에서 상위 노드로 방문을 한다.

상위 노드에서는 하위 노드에서 오는 방문을 모두 False로 초기화 한 후 방문할 때 마다 True로 변환.

상위 노드의 방문처리가 모두 True로 바뀌면 방문 시 cost 중 가장 큰 값을 선택하고 큐에 추가한다.

1. 입력

from collections import deque
import sys
input = lambda : sys.stdin.readline().rstrip()

for _ in range(int(input())):
    
    n,k = map(int,input().split())
    graph = {i: [] for i in range(1,n+1)}
    visit = {i: {} for i in range(1,n+1)}
    visit_cost = {i: {} for i in range(1,n+1)}
    costs = dict(zip(range(1,n+1),map(int,input().split())))
    
    for _ in range(k):
        a,b = map(int,input().split())
        graph[a].append(b)
        visit[b][a] = False
        visit_cost[b][a] = -1

    goal = int(input())

graph에는 노드 a의 상위노드 b 연결

visit과 visit_cost에는 b의 하위노드에서 오는 방문처리와 그 때의 cost 저장. 처음엔 False, -1로 초기화

 

2. BFS

    q = deque() 
    for i in visit:
        if visit[i] == {}:
            q.append((i,costs[i]))

    while q:
        x,cost = q.popleft()
        
        for nx in graph[x]:
            visit_cost[nx][x] = cost
            visit[nx][x] = True

            if all(visit[nx].values()):
                q.append((nx,max(visit_cost[nx].values())+costs[nx]))

큐에 부모가 없는 노드들을 모두 추가한다.

x와 연결된 nx에 cost 업데이트, 방문처리

만약 nx의 모든 하위노드가 방문했다면 큐에 (nx,하위노드 x1,...,xk 최대 + nx 건물 비용)을 추가한다.

주석 다써놓고 최대값으로 안넣어놔서 틀림..

 

3. 출력

    if visit_cost[goal] == {}:
        print(costs[goal])
    else:
        print(max(visit_cost[goal].values()) + costs[goal])

목표 건물과 연결된 노드가 없을 경우 그냥 건물을 지으면 된다.

아닌 경우 연결 노드 중 최대값과 목표건물 비용을 더해서 출력

---

전체코드

from collections import deque
import sys
input = lambda : sys.stdin.readline().rstrip()

for _ in range(int(input())):
    
    n,k = map(int,input().split())
    graph = {i: [] for i in range(1,n+1)}
    visit = {i: {} for i in range(1,n+1)}
    visit_cost = {i: {} for i in range(1,n+1)}
    costs = dict(zip(range(1,n+1),map(int,input().split())))
    
    for _ in range(k):
        a,b = map(int,input().split())
        graph[a].append(b)
        visit[b][a] = False
        visit_cost[b][a] = -1

    goal = int(input())
    
    q = deque() 
    for i in visit:
        if visit[i] == {}:
            q.append((i,costs[i]))

    while q:
        x,cost = q.popleft()
        
        for nx in graph[x]:
            visit_cost[nx][x] = cost
            visit[nx][x] = True

            if all(visit[nx].values()):
                q.append((nx,max(visit_cost[nx].values())+costs[nx]))

    if visit_cost[goal] == {}:
        print(costs[goal])
    else:
        print(max(visit_cost[goal].values()) + costs[goal])

코멘트