[백준(BOJ)] 2623번 : 음악프로그램 - PYTHON[파이썬]

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

2623번: 음악프로그램

 

---

⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

• 그래프 이론
• 위상 정렬

 

---

 

⊙ 문제 접근 과정

 

기본적으로 위상 정렬 알고리즘을 사용한다.

 

이 문제에서는 순서 입력을 아래와 같이 입력받는데 이 부분만 처리해주면 바로 풀린다.

 

가수의 수 -> 가수 순서

 

예를 들어 예제와 같이 3 1 4 3이 들어오면 가수의 수는 3이고 순서는 1 4 3이다.

 

그래서 나는 이것을 list로 받고 1 4를 넣어주고 진입 차수를 하나 올려주고,

다음에는 4 3을 넣어주고 진입 차수를 하나 올려주는 식으로 풀었다.

 

 

 

마지막 조건으로 result 배열의 길이가 v와 같지 않으면 0을 출력

v와 result 배열의 길이가 일치한다면 위상 정렬로 나열한 순서 출력

 

 

 

---

 

⊙ 문제 풀이

 

import sys
from collections import deque

input = sys.stdin.readline

v, e = map(int, input().split())
indegree = [0] * (v + 1)
graph = [[] for i in range(v + 1)]

for _ in range(e):
    temp = list(map(int, input().split()))
    for i in range(len(temp)-2):
        graph[temp[i+1]].append(temp[i+2])
        indegree[temp[i+2]] += 1

result = []
q = deque()

for i in range(1, v + 1):
    if indegree[i] == 0:
        q.append(i)

while q:
    now = q.popleft()
    result.append(now)
    for i in graph[now]:
        indegree[i] -= 1
        if indegree[i] == 0:
            q.append(i)

if len(result) != v:
    print(0)
else:
    for i in result:
        print(i)

 

---

⊙ 결과

 

---

⊙ 마무리

 

 

NONE

 

 

좋아요는 로그인하지 않아도 누를 수 있습니다!