[백준] 2623. 음악프로그램

2623. 음악프로그램

 

• 내 풀이
  • 위상정렬이라는 것을 파악하고 나면 쉬운 문제
  • n번 가수 별로 앞에는 몇 명인지 세고, 뒤로는 누가 있는지 저장
    • 이때 pd 여러 명을 거치면서 중복이 발생할 수 있기 때문에 set 처리
    • → 위상정렬 구현방법을 잊어먹어서 이런식으로 짰는데 더 간단하게 처리 가능
  • 앞 순서 0인 것들부터 진행한 뒤에, 내 뒷타임 진입 차수 -1 해주고 반복

from collections import deque

n, m = map(int, input().split())

indegree = [0 for _ in range(n + 1)]
pre_nodes = [[] for _ in range(n + 1)]
next_nodes = [[] for _ in range(n + 1)]
result = []

for _ in range(m):
    sequence = list(map(int, input().split()))[1:]

    for idx, val in enumerate(sequence):
        next_nodes[val] += sequence[idx + 1:]
        if idx > 0:
            pre_nodes[val] += sequence[:idx]

for idx, pre in enumerate(pre_nodes):
    indegree[idx] = len(set(pre))
next_nodes = [set(nxt) for nxt in next_nodes]

def topological_sort():
    queue = deque()
    for idx, val in enumerate(indegree):
        if idx == 0:
            continue
        if val == 0:
            queue.append(idx)

    while queue:
        x = queue.popleft()
        result.append(x)

        for nxt in next_nodes[x]:
            indegree[nxt] -= 1
            if indegree[nxt] == 0:
                queue.append(nxt)

topological_sort()

if sum(indegree) != 0:
    print(0)
else:
    print(*result, sep='\n')

 

• 다른 사람 풀이
  • 풀이 방식은 동일하나 진입차수 받는 코드가 조금 더 간단함
  • 나는 순서 상관없이 앞에 진행되어야하는 값을 전부 계산해서 넣었다면
  • 이 풀이는 딱 앞 순서꺼만 생각해서 진입차수를 넣어주기 때문에 앞순서의 가수가 0이 되어야 뒷순서 가수의 진입차수도 -1이 되게 됨
  • 중복 제거 해줄 필요가 없음

from collections import deque

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

# 방향 그래프의 모든 간선 정보 입력 받기
for _ in range(m):
    arr = list(map(int, input().split()))
    for i in range(1, len(arr) - 1):
        graph[arr[i]].append(arr[i + 1])
        indegree[arr[i + 1]] += 1


# 위상 정렬 함수
def topology_sort():
    q = deque()
    result = []

    # 시작할 때 진입차수가 0인 노드를 큐에 삽입
    for i in range(1, n + 1):
        if indegree[i] == 0:
            q.append(i)

    while q:
        now = q.popleft()
        result.append(now)

        # 해당 원소와 연결된 노드들의 진입차수에서 1 빼기
        for i in graph[now]:
            indegree[i] -= 1
            # 새롭게 진입차수가 0이 되는 노드를 큐에 삽입
            if indegree[i] == 0:
                q.append(i)

    # 순서를 정하는 것이 불가능한 경우
    if len(result) != n:
        print(0)
    else:
        for singer in result:
            print(singer)

topology_sort()