[BOJ/백준] 14907 프로젝트 스케줄링 - 파이썬

문제

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

 

문제풀이

위상정렬 문제

입력이 특이해서 신경써줘야하는 문제

INPUT을 기준으로 for문을 돌렸으며 개행만 들어올 시 break 하도록 해주었다.

또 알파벳이 입력으로 들어오기때문에 index로 활용하기 위해 ord 변환 해주었다.

 

알고리즘은 보통의 위상정렬 문제와 크게 다를 것이 없으나, result를 구할 때 max 함수로 모든 작업이 끝날때의 시간을 구해줌

 

 

 

코드

import sys
input=sys.stdin.readline
##위상정렬

res=[0]*(26)
graph=[[] for _ in range(26)]
indegree=[0]*(26)
time=[0]*(26)


for INPUT in sys.stdin:
    if INPUT=='\n':
        break
    temp=INPUT.split()
    tmp=ord(temp[0])-65
    time[tmp]=int(temp[1])
    
    prev=list(str(temp[2:]))[2:-2]
    graph[tmp].append(prev)
    for i in prev:
        index=ord(i)-65
        indegree[index]+=1

    
result=0
que=[]
for i in range(26):
    if indegree[i]==0 and time[i]!=0:
        res[i]=time[i]
        result=max(result,res[i])
        que.append(i)
        
while que:
    temp=que.pop()

    for i in range(len(graph[temp][0])):
        index=graph[temp][0][i]
        
        index=ord(index)-65
        indegree[index]-=1

        res[index]=max(res[index],res[temp]+time[index])
        result=max(result,res[index])
            
        if indegree[index]==0:
            que.append(index)
print(result)