[백준 / 1005] ACM Craft - Python

시간 초과로 애를 많이 먹은 문제다..

나의 풀이는 다익스트라(Dijkstra) 알고리즘을 응용하여 풀었으므로 해당 알고리즘을 선행해야 한다.

 

2021.03.18 - [# Coding/# Algorithm] - [보기 쉬운 Algorithm] 다익스트라(Dijkstra) 알고리즘 - Python

[보기 쉬운 Algorithm] 다익스트라(Dijkstra) 알고리즘 - Python

그래프를 입력받은 후 방향을 입력받은 x -> y가 아닌 y -> x로 그려준다. 이는 출발지점이 여러 점일 수 있기 때문에 도착 지점부터 거꾸로 탐색해 나갈 예정이다.

 

또한 건설하기위한 상위 건물이 존재하는데 결국 더 긴 시간을 가지는 상위 건물로 계산을 해주면 된다. 따라서 정확히는 다익스트라 알고리즘이 아니지만 최소가 아닌 최대를 구하는 것으로 변형하여 문제를 풀면 된다.

<입력 >

for _ in range(int(sys.stdin.readline())):
    N, K = map(int, sys.stdin.readline().split())

    D = list(map(int, sys.stdin.readline().split()))
    graph = {i+1: [] for i in range(N)}
    for i in range(K):
        x, y = map(int, sys.stdin.readline().split())

        if x not in graph[y]:
            graph[y].append(x)

    W = int(sys.stdin.readline())

    print(R_dijkstra(graph, D, W))

 

먼저 테스트 케이스만큼 큰 for문을 반복해준다.

 

건물의 개수 N과 건물 건설 규칙 K를 입력받고, 각 건물의 건설 시간인 D를 list에 저장해준다.

 

graph에 모든 노드의 key를 선언해주고, value는 빈 list로 구현해준다. 그리고 목적지 건물부터 처음으로 올라갈 예정이므로 x, y를 입력받아 방향을 반대로 그래프를 그려준다.

 

목적 건물인 W를 입력받고, 함수에 graph, D(건물 건설 시간), W(출발 건물)을 넘겨준다.

<함수1>

from collections import deque
import sys


def R_dijkstra(graph, D, start_node):
    times = {i: -1 for i in graph}
    times[start_node] = D[start_node-1]
    maxTime = D[start_node-1]
    queue = deque()
    queue.append([times[start_node], start_node])

 

알고리즘의 시간을 단축시키기 위해서 list가 아닌 deque를 사용한다. 또한 입력의 경우도 많을 수 있으므로 input보다 빠른 sys.stdin.readline을 사용한다.

 

최단 거리를 구하는 다익스트라 알고리즘과 반대로 최대를 구하기 때문에 R_dijkstra로 이름을 정했다.

 

times에는 start_node로 부터 해당 건물까지 건설에 걸리는 총 시간을 넣을 것이ㅏㄷ. 최대 시간을 구해야 하므로 time의 모든 건물의 걸리는 시간을 -1로 설정하여 값이 더 크면 갱신할 것이다.

 

처음 시작 건물의 times을 해당 건물의 건설시간에서 구한다. D에는 건설 시간이 담겨있고, [start_node - 1]의 이유는 n번째 건물의 건설 시간은 D[n-1]에 담겨있기 때문이다.

 

결론적으로 최대시간을 구하는 것이므로 maxTime이라는 변수를 선언해주고 현재 가장 큰 시간인 start_node의 시간으로 초기화해준다.

 

시간단축을 위해 queue를 deque로 선언하고, [총 걸린 시간, 현재 노드(건물)]을 넣는다.

<함수2>

	while queue:
        current_time, current_node = queue.popleft()

        if current_time < times[current_node]:
            continue

        for next_node in graph[current_node]:
            new_time = current_time+D[next_node-1]
            if new_time > times[next_node]:
                times[next_node] = new_time
                if new_time > maxTime:
                    maxTime = new_time
                queue.append([new_time, next_node])

    return maxTime

 

queue가 존재하는 동안 while문을 반복한다.

 

queue에서 현재 진행 시간과, 현재 노드를 받아오고, 만약 현재 시간이 times에 있는 해당 건물의 시간보다 짧다면 해당 값들을 무시하고 while문을 건너뛰어 다음 값을 받아온다.

 

그렇지 않다면 다음 노드를 graph에서 받아와 해당 건물까지 지어지는 시간을 계산하여 new_time이라는 변수에 저장하는데, 해당 값이 times에 있는 값보다 크다면 times의 값을 갱신하고, 우리가 알고싶은 max_time보다도 크다면 이 값도 갱신해준다. 그리고, 연결된 노드를 queue에 넣어주어 끝까지 반복한다.

 

이것을 반복하면 제일 긴 시간이 나오므로 해당 값을 반환해준다.

 

<전체코드>

from collections import deque
import sys


def R_dijkstra(graph, D, start_node):
    times = {i: -1 for i in graph}
    times[start_node] = D[start_node-1]
    maxTime = D[start_node-1]
    queue = deque()
    queue.append([times[start_node], start_node])

    while queue:
        current_time, current_node = queue.popleft()

        if current_time < times[current_node]:
            continue

        for next_node in graph[current_node]:
            new_time = current_time+D[next_node-1]
            if new_time > times[next_node]:
                times[next_node] = new_time
                if new_time > maxTime:
                    maxTime = new_time
                queue.append([new_time, next_node])

    return maxTime


for _ in range(int(sys.stdin.readline())):
    N, K = map(int, sys.stdin.readline().split())

    D = list(map(int, sys.stdin.readline().split()))
    graph = {i+1: [] for i in range(N)}
    for i in range(K):
        x, y = map(int, sys.stdin.readline().split())

        if x not in graph[y]:
            graph[y].append(x)

    W = int(sys.stdin.readline())

    print(R_dijkstra(graph, D, W))