[알고리즘 문제 풀이][파이썬] 백준 1005번: ACM Craft

백준 1005 문제 링크: https://www.acmicpc.net/problem/1005

📑 문제 설명
1. 여러 개의 지을 건물이 주어짐
2. 지을 건물들은 각각 건축 시간이 존재
3. 건물을 지을 때는 일련의 규칙이자 순서를 따라야 함
4. 1번 건물을 다 지은 후 이어진 건물이 차례로 지어짐
--> 지으려는 건물 단계에서 이전 단계의 건물이 지어지지 않을 경우 다음 단계 건물은 지어질 수 없음
5. 지으려고 목표하는 건물의 번호가 주어지면 그 건물이 지어지기 위한 시간을 구함

이 이미지에서는 4번 건물을 짓기 위해서 반드시 2, 3번 건물이 지어져야 하며 2, 3번 건물이 지어지기 위해서 반드시 1번 건물이 지어져야 함. 2, 3번 건물은 같은 순서를 가지고 있기 때문에 동시에 지을 수 있으며 따라서 100초가 걸림

입력: 첫째 줄에 테스트 케이스가 주어지고 둘째 줄에 건물의 개수(N)와 건물 간의 건물 순서 규칙 개수(K)가 주어진다. 셋째 줄에는 주어진 각 건물의 건축시간이 공백을 기준으로 주어지고 넷째 줄부터 건물규칙이 주어진다. 건축 규칙이 다 주어진 후 마지막 줄에 지으려는 건물(목표하는 건물)의 번호가 주어진다.

출력: 목표하는 건물을 짓기 까지 소요되는 시간

💡 문제 해결 방법
알고리즘: BFS, 위상정렬

알고리즘 선택 이유

• 같은 depth를 갖는 node를 체크해야 하기 때문에 bfs가 적합하다고 판단
• depth가 중요하지 않음. 나에게 들어오는 edge가 있는지, 없는지가 중요하기 때문에 위상정렬 알고리즘 사용

예외처리
1. 목표하는 건물 번호에 도달할 경우 종료
2. bfs에서 현재 노드에 연결된 노드 반복문을 돌릴 때마다 같은 depth를 공유하는 건물 중 가장 오랜 시간을 기억 및 누적합 계산
3. 지금 현재 닥친 문제
1
4 3
10 1 100 20
1 2
2 3
4 3
3
정답: 120

내가 작성한 방법으로는 111, 즉, 4번 건물을 짓고 나서 3번을 지어야 하는데 4번을 체크하지 못함

스터디 내용

• 싸이클이 발생하면 문제 풀이가 안됨
• 그래프가 Directed Graph이므로 위상정렬 문제
• BFS
• in edge 수를 카운트하여 in edge 가 0인 애들부터 탐색(queue 이용)

💻 코드

import sys
from collections import deque

def bfs(queue, inedge, timerecord):
    while(queue):
        v = queue.popleft()
        time = timerecord[v]
        for nv in graph[v]:
            inedge[nv] = inedge[nv] - 1
            if inedge[nv] == 0:
                queue.append(nv)
            timerecord[nv] = max(timerecord[nv], time + timelist[nv])

    print(timerecord[w])

test = int(sys.stdin.readline())
for t in range(test):
    n, k = list(map(int, sys.stdin.readline().split()))
    timelist = [-1] + list(map(int, sys.stdin.readline().split()))
    graph = {}
    inedge = {} # 한 건물이 지어지기 위해서 지어야 하는 이전 건물의 개수(들어오는 edge의 수)
    for i in range(1, n+1):
        graph[i] = []
        inedge[i] = 0
    for i in range(k):
        x, y = list(map(int, sys.stdin.readline().split())) # x를 지은 다음에 y를 짓는다
        graph[x].append(y)
        inedge[y] +=1
    w = int(sys.stdin.readline())

    queue = deque()
    timerecord = [-1] + [0 for x in range(1, n+1)]
    for i in range(1, n+1):
        if inedge[i] == 0:
            queue.append(i)
            timerecord[i] = timelist[i]
    bfs(queue, inedge, timerecord)

💟 추가적으로 알게 된 점

• BFS 문제 풀면서 느끼는 점은 queue에 막 집어 넣게 되는 순간 바로 메모리 or 시간초과나기 때문에 무조건 queue에 들어가는 조건에 대해 생각해봐야 함.
• 위상정렬 문제는 cycel이 없고 directed 일 때 풀 때 사용하는 알고리즘으로 queue에 탐색할 원소를 넣을 때의 조건은 'inedge가 0일 경우" 이다.