[백준] 1005 ACMCraft (python 파이썬)

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

1005번: ACM Craft

 

풀이 과정

처음에 for 문을 사용해서 풀었다. 예제 기준으로 1 2 3 4처럼 순서대로인 경우는 정답이 맞지만.

3 -> 2 -> 1과 같이 순서가 거꾸로인 경우 답이 틀리게 나온다.

순서를 내가 원하는 대로 정하면 해결이 될 거 같아 방법을 찾아보던 도중 위상 정렬이라는 것을 알았다.

 

큐를 사용해서 진입 차수가 0인 것들을 그래프에서 pop해주며 정렬해주면 된다.

위 그림을 보면 node 1 ~ 4까지 진입 차수가 각각 0 1 1 2이다. 이러면 진입 차수가 0인 node 1을 큐에 넣고 node 2, 3의 진입 차수를 1 감소 시켜 주면 된다. 이후 진입 차수가 0이 된 node 2, 3을 큐에 넣는다. 이 동작을 반복하면 위상 정렬을 한다. 

 

node 4와 같이 진입 차수가 2 이상인 경우가 있다. 이 경우 node 4의 건설 완료 시간을 계산 할때 node 2와 3가 건설될 때까지 시간 중 오래 걸리는 시간을 더해주면 된다.

 

 

from collections import deque
import sys

input = sys.stdin.readline
T = int(input().rstrip())

for _ in range(T):
    N, K = map(int,input().rstrip().split())

    D = [0]
    D.extend([int(x) for x in input().rstrip().split()]) # n번째 건물 건설 시간
    in_degree = [0 for _ in range(N + 1)] # n번째 node 진입 차수
    adj_list_out = [[] for i in range(N + 1)] # n번째 노드에서 out인 노드 저장
    adj_list_in = [[] for i in range(N + 1)]  # n번째 노드에서 in인 노드 저장
    deq = deque()
    toposort = []
    Dtime = [0 for i in range(N + 1)] # n번째 건설까지 소요되는 시간

    for i in range(K):
        x, y = map(int,input().rstrip().split())
        adj_list_out[x].append(y)
        adj_list_in[y].append(x)
        in_degree[y] += 1
    W = int(input())

 

 주어진 입력값들을 제외 하고 설명하면 위상 정렬하기 위해 in_dgree와 adj_list_out 리스트를 선언해준다.

정렬된 값들은 toposort 리스트에 저장해준다. Dtime은 n번째 건물까지 걸리는 시간을 저장해준다.

 

 

    for i in range(1,N + 1):
        if in_degree[i] == 0:
            deq.append(i)

    while deq:
        node = deq.popleft()
        toposort.append(node)
        for s in adj_list_out[node]:
            in_degree[s] -= 1
            if in_degree[s] == 0:
                deq.append(s)

이 파트는 위상 정렬을 위한 코드다. 가장 먼저 진입 차수가 0인 값들을 큐에 넣어준다.

이후 큐가 완전히 비워질때까지 node들을 하나씩 pop 하면서 해당 노드와 연결된 다른 노드들의 indegree값들을 감소시켜준다.

감소시킨 이 후 그 노드의 진입 차수가 0이 되면 큐에 추가해준다.

 

 

    for i in toposort:
        count = 0
        for b in adj_list_in[i]:
            if count < Dtime[b]:
                count = Dtime[b]
        Dtime[i] = D[i] + count

    print(Dtime[W])

정렬된 순서에 따라 건물들이 지어지는 시간을 계산하면 된다. node i에 대해 i전까지 걸리는 시간들 중 최댓값을 

D [i]에 더해주면 된다. 이후 문제에서 요구한 건물의 건설 시간을 출력한다.

 

 

전체 코드

from collections import deque
import sys

input = sys.stdin.readline
T = int(input().rstrip())

for _ in range(T):
    N, K = map(int,input().rstrip().split())

    D = [0]
    D.extend([int(x) for x in input().rstrip().split()]) # n번째 건물 건설 시간
    in_degree = [0 for _ in range(N + 1)] # n번째 node 진입 차수
    adj_list_out = [[] for i in range(N + 1)] # n번째 노드에서 out인 노드 저장
    adj_list_in = [[] for i in range(N + 1)]  # n번째 노드에서 in인 노드 저장
    deq = deque()
    toposort = []
    Dtime = [0 for i in range(N + 1)] # n번째 건설까지 소요되는 시간

    for i in range(K):
        x, y = map(int,input().rstrip().split())
        adj_list_out[x].append(y)
        adj_list_in[y].append(x)
        in_degree[y] += 1
    W = int(input())

    for i in range(1,N + 1):
        if in_degree[i] == 0:
            deq.append(i)

    while deq:
        node = deq.popleft()
        toposort.append(node)
        for s in adj_list_out[node]:
            in_degree[s] -= 1
            if in_degree[s] == 0:
                deq.append(s)

    for i in toposort:
        count = 0
        for b in adj_list_in[i]:
            if count < Dtime[b]:
                count = Dtime[b]
        Dtime[i] = D[i] + count

    print(Dtime[W])

 

추가)

    for i in range(1,N + 1):
        if in_degree[i] == 0:
            deq.append(i)
            Dtime[i] = D[i] #

    while deq:
        node = deq.popleft()
        toposort.append(node)
        for s in adj_list_out[node]:
            in_degree[s] -= 1
            Dtime[s] = max(Dtime[s],Dtime[node] + D[s]) #
            if in_degree[s] == 0:
                deq.append(s)

while문에서 DP를 이용해 해결하면 좀 더 효율적으로 문제를 해결할 수 있다.

큐를 뺄 때마다 이전 Dtime값이랑 이전 건물까지 건설하는 데 걸린 시간 + 이번 건물 짓는 시간을 비교하여 큰 값을 저장해준다.

큰값을 구하는 이유는 건물을 짓기 위해선 이전 건물들을 전부 지어야 하기 때문에 가장 큰 값을 선택하여 저장한다.