백준 1005 [ACM CRAFT] 파이썬

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

 

 

드디어 1005번 ACM CRAFT를 풀었다..

 

# 백준 1005 ACM Craft

import sys
sys.setrecursionlimit(10**7)       # 재귀 한도 확장 (깊은 DFS 대비)
input = sys.stdin.readline          # 빠른 입력

T = int(input())                    # 테스트 케이스 수

def dfs(W):
    # W 건물을 짓기 위해 필요한 이전 건물들이 있으면
    if graph[W]:
        # 각 이전 건물(prev_build)에 대해
        for prev_build in graph[W]:
            # 아직 계산하지 않은 경우 재귀 DFS 호출
            if not visited[prev_build]:
                dfs(prev_build)
                visited[prev_build] = True      # 계산 완료 표시
            # 현재 건물 W의 소요시간은 이전 건물까지 걸린 시간 + W 건물 소요시간 중 최대값
            costs[W] = max(costs[W], costs[prev_build] + needed_time[W])
    else:
        # 이전 건물이 없는 경우 (시작 건물)
        costs[W] = needed_time[W]

for _ in range(T):
    N, K = map(int, input().split())          # 건물 개수 N, 규칙 개수 K
    needed_time = [0] + list(map(int, input().split()))   # 각 건물 짓는 데 걸리는 시간 (1-based)
    costs = [0 for _ in range(N+1)]            # 각 건물을 짓는데 걸리는 총 시간 저장용
    graph = [[] for _ in range(N+1)]           # 이전 건물 정보 그래프 (뒤에서부터 연결)
    visited = [False for _ in range(N+1)]      # 방문 및 계산 완료 여부

    # 건설 규칙 입력 (needed_build -> can_build 순서)
    for _ in range(K):
        needed_build, can_build = map(int, input().split())
        graph[can_build].append(needed_build)

    W = int(input())                           # 최종 목표 건물
    dfs(W)                                    # 목표 건물까지 걸리는 시간 계산
    ans = costs[W]
    print(ans)                                # 결과 출력

 

풀긴했지만, 시간초과가 발생할 수도 있는 문제점이 있는 코드이다.

DFS 호출하고나서 재귀적으로 계속 DFS가 호출되지만 visited는 모든 재귀호출이 끝나야 호출되기 때문에 시간초과가 발생가능하다. 따라서 visited를 처음 방문하는 경우 제외하고는 값을 리턴하도록 하여 중복 계산하지 않도록 처리한다.

(사이클이 있는 경우는 사이클 파악을 위해 visiting, calculated 두 배열을 생성하여 분리하는게 좋다.)

GPT가 제시한 개선된 코드를 첨부한다.

 

import sys
sys.setrecursionlimit(10**7)       # 재귀 깊이 제한 확장 (깊은 DFS 대비)
input = sys.stdin.readline          # 빠른 입력

T = int(input())                    # 테스트 케이스 수

def dfs(node):
    if visited[node]:               # 이미 계산 완료된 노드면
        return costs[node]         # 저장된 결과 반환

    visited[node] = True            # 계산 시작 표시 (방문 처리)
    max_prev = 0                   # 이전 건물들 중 최대 건설 시간 저장 변수

    for prev in graph[node]:        # node를 짓기 전에 지어야 하는 모든 건물들 순회
        max_prev = max(max_prev, dfs(prev))  # 최대 건설 시간 갱신

    costs[node] = max_prev + needed_time[node]  # 현재 건물 건설 시간 더해서 저장
    return costs[node]             # 현재 노드 완성까지 걸리는 시간 반환

for _ in range(T):
    N, K = map(int, input().split())               # 건물 개수 N, 건설 규칙 개수 K
    needed_time = [0] + list(map(int, input().split()))  # 각 건물 건설 시간 (1-indexed)
    costs = [0] * (N + 1)                          # 각 건물까지 걸리는 총 시간 저장용
    visited = [False] * (N + 1)                     # 방문 및 계산 완료 여부
    graph = [[] for _ in range(N + 1)]             # 그래프 (간선: 선행 건물 -> 현재 건물)

    for _ in range(K):
        needed_build, can_build = map(int, input().split())
        graph[can_build].append(needed_build)      # can_build 짓기 전에 needed_build 먼저 지어야 함

    W = int(input())                               # 목표 건물
    print(dfs(W))                                  # 목표 건물까지 걸리는 최소 시간 출력

DAG (Direct Acyclic Graph), 사이클 없는 방향그래프 경우에는 DP+DFS를 고려해보자!