[백준] 1005번 ACM CRAFT 파이썬 코드

코드1

# BFS로 해결

import sys
from collections import deque
input = lambda: sys.stdin.readline().rstrip() # 람다함수로 사용
tc = int(input())

def bfs(s,g,v,t):
  queue = deque([s])
  v[s] = t[s]
  endpoint = [] # 끝에 도달한 값을 모아줄 리스트
  while queue:
    popnum = queue.popleft()
    if g[popnum]: # 올라갈 값이 있는 경우
      for i in g[popnum]:
        if v[i] < v[popnum]+t[i]: # 큰값으로 초기화
          v[i] = v[popnum]+t[i]
          queue.append(i)
    else: endpoint.append(popnum) # 끝까지 도달한 경우
  return endpoint
for _ in range(tc):
  n,k = map(int, input().split())
  time = [0, *map(int, input().split())] # 숫자를 맞춰주기 위해 0 추가
  graph = [[]*(n+1) for _ in range(n+1)]
  visited = [0]*(n+1)
  for _ in range(k):
    x,y = map(int, input().split())
    graph[y].append(x) # 역방향으로 구성
  w = int(input()) # 찾을 값
  end = bfs(w, graph, visited, time)
  print(max(visited)) # 반환된 리스트에서 가장 큰 값을 찾아주면 정답

아이디어

역방향으로 가서 끝까지 올라간 값들을 모아준 후, 거기서 가장 큰 값을 출력해준다.
이게 가능한 이유는 사이클이 없기 때문에 그대로 거슬러 올라갈 수 있기 때문이다.
순방향 bfs로는 풀 수 없는 이유는? => 연결 요소가 하나라는 보장이 없다. 즉, 따로 떨어져 있는 경우에 그 건물을 짓는 시간을 출력해주어야 하는데 순방향으로 가면 0이 출력된다.

이는 역방향으로 올라가는 것으로 해결 가능하다.

 

위상정렬에 대한 개념 부재로 인해 정해보다 조금 더 복잡하게 푼 문제.

 

코드 2

# 유향 비순환 그래프이므로 위상정렬 사용 가능

import sys
from collections import deque
input = sys.stdin.readline

def topol_sort(g,v,t,i): # 위상정렬
  queue = deque([])
  for j in range(1,n+1): # 전입차수가 0인 경우 덱에 추가
    if i[j] == 0:
      v[j]=t[j] # visite의 값은 해당 건물이 지어지는 시간
      queue.append(j)
  while queue:
    popnum = queue.popleft()
    for l in g[popnum]:
      v[l] = max(v[l],v[popnum]+t[l]) # 값 비교를 통해 더 큰 값을 저장
      i[l]-=1 # 간선 한 개 제거
      if i[l] == 0:queue.append(l) # 전입되는 간선이 없는 경우 덱에 추가

tc = int(input())
for _ in range(tc):
  n,k = map(int, input().split())
  graph = [[] for _ in range(n+1)]
  visited = [0]*(n+1)
  indegree = [0]*(n+1)
  time = [0, *map(int, input().split())] # 편의를 위해 가장 앞에 0 추가
  for _ in range(k):
    x,y = map(int ,input().split())
    graph[x].append(y) # 지어져야하는 건물 추가
    indegree[y] += 1 # 전입차수 + 1
  w = int(input())
  topol_sort(graph, visited,time,indegree)
  print(visited[w])

위상정렬 코드 추가