[백준/BOJ] 2623번 - 음악프로그램 (Python)

· 문제링크

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

2623번: 음악프로그램

· 핵심 : 위상 정렬 - 「 in-degree를 활용한 방법」

1.  방향성이 존재하는 그래프 생성 & 들어오는 간선 수 기록

→  3 1 4 3 

→ 3 : 가수의 수, 1 4 3 : 가수의 번호

→ 1 - 4 / 4 - 3 으로 그래프 연결

 

2. in-degree = 0인 후보들 적절한 자료구조(리스크, 큐, 스택, 힙 등)에 넣기

 

3. candiates가 전부 비워질 때까지 확인하기

→ candidates에 존재하는 후보군 하나씩 빼면서 연결된 in-degree 1개 제거 

→ 1개 제거 했을 때 만약 in-degree가 0이 된다면 candidates에 넣기

---

· 코드(Python)

# https://www.acmicpc.net/problem/2623
n, m = map(int, input().split())
adj = [[] for _ in range(n + 1)]
ind = [0 for _ in range(n + 1)]

for _ in range(m):
    nums = list(map(int, input().split()))
    for i in range(1, nums[0]):
        # 그래프 생성 - 방향성 존재
        adj[nums[i]].append(nums[i + 1])
        # 진입하는 경우 in-degree 증가
        ind[nums[i + 1]] += 1

# in-degree = 0 후보군 넣기
candidates = []
for i in range(1, n + 1):
    if ind[i] == 0:
        candidates.append(i)

result = []
while candidates:
    # 후보군에서 추출
    cur = candidates.pop()
    result.append(cur)
    # 추출 후 연결된 다음 노드들의 in-degree 제거
    for nxt in adj[cur]:
        ind[nxt] -= 1
        if ind[nxt] == 0:
            candidates.append(nxt)

if len(result) != n:
    print(0)
else:
    for num in result:
        print(num)