[BOJ/Python] 백준 2623 음악프로그램

문제

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

풀이

풀이

• 34128 KB, 64 ms

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

n, m = map(int, input().split())  # n : 가수의 수, m : 보조 PD의 수

graph = [[] * (n + 1) for _ in range(n + 1)]
indegree = [0] * (n + 1)
q = deque()
ans = []

for _ in range(m) :
    tmp = list(map(int, input().split()))
    x = tmp[0]  # 담당한 가수의 수

    if x <= 1 : continue

    # 선행 관계 넣어주기
    # 보조 출연자 순서 : tmp[1] 부터(포함) x개 -> x-1개까지 쌍
    for i in range(1, x) :
        if tmp[i + 1] not in graph[tmp[i]] :
            graph[tmp[i]].append(tmp[i + 1])
            indegree[tmp[i + 1]] += 1

# 선행 조건 없는거 q에 넣어주기
for i in range(1, n + 1) :
    if indegree[i] == 0 : q.append(i)

# q 빌 때까지 반복문
isCycle = False
while q and not isCycle :
    cur = q.popleft()
    ans.append(cur)

    for nxt in graph[cur] :

        if cur in graph[nxt] : # 사이클 있으면 종료
            isCycle = True
            break

        indegree[nxt] -= 1 # 선행조건 하나 해결

        if indegree[nxt] == 0 : q.append(nxt)

if len(ans) == n :
    for a in ans : print(a)
else : print(0)

풀이 설명

• 사이클이 있을 수 있는! 위상정렬 문제 -> 사이클 있는지 판단해야 한다
• 사이클 판단 방법

        if cur in graph[nxt] : # 사이클 있으면 종료
            isCycle = True
            break

: cur이 nxt의 선행 조건인데, nxt도 cur의 선행 조건

그런데.. 사실 이렇게 안해도 된다.

사이클이 있으면 정답 리스트에 1 ~ n이 모두 들어오지 않기 때문!

풀이2

• 참고 풀이
• 34160 KB, 68 ms

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

n, m = map(int, input().split())
graph = [[] * (n + 1) for _ in range(n + 1)]
indegree = [0] * (n + 1)
ends = set(range(1, n + 1))
q = deque()
ans = []

for _ in range(m) :
    tmp = list(map(int, input().split()))

    l = tmp[0]

    for i in range(1, l) :
        graph[tmp[i]].append(tmp[i + 1]) # 선행관계인 요소 추가
        indegree[tmp[i + 1]] += 1 # 진입차수 ++
        ends.discard(tmp[i + 1])

# 입력 끝

ends = list(ends) # 진입차수 0인 요소만 남음
for e in ends : q.append(e)  # 진입차수 0인 요소 큐에 넣기

while q :
    cur = q.popleft()
    ans.append(cur)

    for nxt in graph[cur] : # 후순이 요소
        indegree[nxt] -= 1 # 선행 요소 하나 완료

        if indegree[nxt] == 0 : q.append(nxt)  # 선행 요소 다 끝나면 큐에 넣기

if len(ans) == n :
    print('\n'.join(map(str, ans)))
else :
    print(0)

배운 점

파이썬

• 1 ~n 들어있는 set 만들기 : set(range(1, n + 1))
• set 메소드 remove vs discard : 둘 다 요소를 제거하는 메소드
  • remove는 제거할 요소가 없으면 오류가 발생하지만 discard는 없어도 정상 종료
• 리스트 요소 한 줄에 하나 씩 출력하기 : print(‘\n’.join(map(str, ans)))

알고리즘 : 위상 정렬

• 1~n이 unique하게 들어있는 리스트를 만들고, 선행조건 추가될 때 제거하면 for문 이용하지 않고도 진입차수 0인 요소들 찾을 수 있다 !!!