백준 20119 클레어와 물약

문제

👀 문제 사이트 : https://www.acmicpc.net/problem/20119

풀이

난이도 : GOLD I

이 문제는 기본적인 위상정렬이 아닌 list 에 차수를 두어 풀이하였다.

처음에는 모든 레시피를 계속 반복하면서 만족하는 레시피가 있으면 물약을 만드는 과정을 반복하여 풀이를 시작하였지만 시간 초과가 발생하였다.

다음으로 시도해본 방법이 차수를 적용한 위상 정렬이다.
위상 정렬 기본 문제와 다르게 물약을 만드는 레시피 목록에 차수를 두어 풀이를 진행하였는데, 순서는 다음과 같다.

입력
3 1 5 7 2 -> 개수, 물약1, ..., 물약 n, 만들어질 물약

1) 물약들로부터 만들어지는 다음 물약과 해당 레시피 정보를 저장하고 레시피 차수를 적용한다.
2) 이미 가지고 있는 물약으로 차수 감소를 적용하고, 차수가 0인 레시피를 queue 에 push 한다.
3) 이후에는 기본적인 위상정렬과 비슷하게 레시피로 만들 다음 물약에 대해서 차수 감소를 진행하며 반복한다.
4) 주의할 점 : 이미 적용했던 물약의 경우 반복하지 않도록 해야 한다.

코드

from collections import deque
import sys

input = sys.stdin.readline
n, m = map(int, input().split())

# 물약 사용 여부
visited = [False] * (n + 1)
# nxt_recipe[i] : (i번 물약을 통해 다음으로 갈 수 있는 물약의 번호, 해당 레시피 번호) 의 리스트
nxt_recipe = [[] for _ in range(n + 1)]
# 레시피의 차수
indegree = [0] * (m + 1)
# 레시피 정보
recipe_info = []

# 위상정렬을 위한 queue
q = deque()

# 레시피 내용 반영
for j in range(m):
    inputs = list(map(int, input().split()))

    for i in range(1, len(inputs) - 1):
        # inputs[i] -> inputs[-1] : topological sort
        nxt_recipe[inputs[i]].append((inputs[-1], j))
        indegree[j] += 1
    
    recipe_info.append(inputs[1:])

# 현재 가지고 있는 물약의 개수
l = int(input())

# 현재 가지고 있는 물약
result = list(map(int, input().split()))

# 현재 물약을 가지고 레시피들의 차수 계산
for liquid in result:
    # 물약 사용 여부 체크
    visited[liquid] = True

    # 해당 물약으로부터 다음 물약으로 갈 수 있는 레시피 차수 감소
    for next in nxt_recipe[liquid]:
        indegree[next[1]] -= 1
        if indegree[next[1]] == 0:
            # 레시피 차수가 0이라면 진입이 가능하므로 레시피 번호에 있는 입력 레시피 삽입
            q.append(recipe_info[next[1]])

# 위상 정렬
while q:
    r_info = q.popleft()
    
    # 만들어질 물약이 이미 사용되었을 경우 continue
    if visited[r_info[-1]]:
        continue
    
    # 물약 사용 체크
    visited[r_info[-1]] = True
    # 결과에 값 기록
    result.append(r_info[-1])

    # 해당 물약으로부터 다음 물약으로 갈 수 있는 레시피 차수 감소
    for next in nxt_recipe[r_info[-1]]:
        indegree[next[1]] -= 1
        if indegree[next[1]] == 0:
            # 레시피 번호에 있는 입력 레시피 삽입
            q.append(recipe_info[next[1]])

# 결과 출력
print(len(result))
print(' '.join(map(str, sorted(result))))