백준 1005번 ACM Craft

백준 1005번 ACM Craft 문제

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

파이썬 코드

import sys
from collections import deque

T = int(sys.stdin.readline())
result = []

for i in range(T):
  N, K = map(int, (sys.stdin.readline().split()))
  D = list(map(int, sys.stdin.readline().split()))
  graph = {i : [] for i in range(1, N+1)}
  
  indegree =[0 for _ in range(N)]
  for j in range(K):
    start, end = map(int, sys.stdin.readline().split())
    graph[start] += [end]
    indegree[end-1] += 1
  
  deq = deque()
  order = []

  for v in range(N):
    if indegree[v] == 0:
      deq.append(v+1)

  while deq:
    node = deq.popleft()
    
    for number in graph[node]:
      indegree[number-1] -= 1
      if indegree[number-1] == 0:
        deq.append(number)

    order.append(node)
    
  W = int(sys.stdin.readline())

  board = [0 for _ in range(N+1)]
  complete = []
  
  for start in order:
    board[start] = board[start] + D[start-1]   
    
    for end in graph[start]:
      board[end] = max(board[end], board[start])   
  
  result.append(board[W])

for number in result:
  print(number)

풀이법

이 문제를 처음보고 생각났던 것은 다음과 같다.

• 다익스트라?
• BFS? DFS?

열심히 코드를 짜고 제출했으나 '틀렸습니다.'가 나왔다.

반례를 생각해보니 건물이 지어지는 관계를 순서대로 주지 않는 경우가 생각이 났다. 이는 건물이 순서대로 지어진다는 가정하에 풀었던 것인데 실제로는 건물이 1 > 2 > 3 > 4 이렇게 오름차순으로 지어져야만 하는게 아니다. 또한 건물 관계도 순서대로 주어지지 않는 경우가 있다.

이를 정리해서 풀려면 우선 graph 자체를 dictionary로 받아서 건물 관계도 순서를 무시하는 일이다.

또한 건물의 지어지는 순서가 주어지지 않는다면 그래프의 관계로 지어지는 순서를 알아야한다.

• 여기서 나오는 것이 위상정렬이다.

위상정렬

위상정렬이란?

그래프가 주어지고 순서가 정해져 있는 작업'을 차례로 수행해야 할 때, 순서를 결정할 때 사용하는 알고리즘이다. 하나의 방향 그래프에는 여러 개의 위상 정렬이 가능하다.

위상정렬의 조건

1. 위상 정렬을 할 그래프는 간선이 방향성을 가지는(유향) 그래프여야 한다.
2. 그래프 내부에 순환(cycle)이 있으면 안된다.

알고리즘 원리

진입 차수라는 개념이 나온다. 그래프에서 자신의 노드에 도착하는 간선의 개수를 뜻하는 말이다.

그래프의 순서를 구하기 위해서는 진입 차수를 작은 순서대로 그래프의 관계를 고려하여 나열하면 되는 것이다.

1. 우선 각 그래프의 진입 차수를 구한다.
2. 진입 차수가 0인 노드를 deque에 넣는다.
3. popleft()로 노드를 하나 꺼내고 해당 노드를 출발점으로 도착하는 노드들의 진입 차수를 하나씩 마이너스한다. (해당 노드와 노드를 통해서 나온 간선들을 제거하는 과정이다.)
4. 이때 해당되는 노드들이 만약에 진입 차수가 0이 된다면 deque에 넣어준다.
5. order에 꺼낸 노드를 넣어준다.