[백준] [BFS] [위상정렬] 2056. 작업

2056. 작업

2056번: 작업

 

• 4%에서 계속 틀려서 되게 애먹은 문제...
  • 전입차수가 없거나 동일한게 여러개 있다는 것 잊지말기!
  • 시작도 여러개, 끝도 여러개가 동시에 될 수 있음!!
• 틀린 이유
• 1.  전입차수가 0인게 1만 있는건 아니므로 전체 돌면서 queue에 넣어줘야 0인값들이 먼저 시작됨.
  2. 전부 전입차수가 없을 수 있고,
     마지막 순서값도 하나가 아닐 수 있기때문에 solve문 안에서 if절로 return할수 없음
     • → 나와서 max(visited)로 확인
  3. 현재값의 시간까지 더해서 비교하지 말고, 전입값들 크기로만 비교해서 다음값 (visited[gp]) 갱신해두기
     • → 그래야 시간단축
     • 전입차수 개수가 0이 되면 그때 현재값까지 더해서 저장

#사용했던 반례
7
5 0
3 0
6 0
1 0
8 0
4 0
2 0

#결과
8

• 내 풀이

from collections import deque

def solve():
    global n
    global result
    queue = deque()

    #전입차수가 0인게 1만 있는건 아니므로 전체 돌면서 queue에 넣어주기
    for i in range(1,n+1):
        if inlst[i]==0:
            visited[i]=time[i]
            queue.append(i)

    while queue:
        k= queue.popleft()

        for gp in graph[k]:
            if inlst[gp]!=0:
                inlst[gp] -= 1
            #전입값들을 현재값에 넣으면서 계속 갱신
            visited[gp]=max(visited[gp],visited[k]) 
            if inlst[gp] == 0:
                #위에서 전입값
                visited[gp]+=time[gp]
                queue.append(gp)


n = int(input())
# 진입차수 개수
inlst = [0 for i in range(n + 1)]
time = [0 for i in range(n + 1)]
graph = [[] for i in range(n + 1)]
visited=[0 for i in range(n+1)]

for i in range(1, n + 1):
    # 걸린 시간, 선행작업 개수, 작업 번호
    tmp = list(map(int, input().split()))
    time[i] =  tmp[0]
    inlst[i] =  tmp[1]
    for l in tmp[2:]:
        graph[l].append(i)


solve()

#전부 전입차수가 없을 수 있고
#마지막 순서값도 하나가 아닐 수 있기때문에 solve문 안에서 if절로 return할수 없음
print(max(visited))