[BOJ/백준] 2252. 줄 세우기 (Python)

🔎 문제

🔗 백준 2252번 줄 세우기

💡 풀이

두 학생들끼리의 키의 순서만 바뀌지 않으면 되므로 간선의 방향만 틀리지 않게 정렬하면 되는 위상정렬이 적합하다.

위상정렬을 구현하는 방법은

1. 진입차수에 대한 배열을 만든다.
2. 진입차수를 초기화 한다.
3. 진입차수가 0인 노드를 큐에 넣는다.
4. 큐에서 노드를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다. (이 과정에서 간선을 따라 다다른 노드의 진입차수를 1씩 감소시킨다)
5. 새롭게 진입차수가 0이 된 노드들을 큐에 넣는다.
6. 3~5번을 큐가 빌 때까지 반복한다.

로 간단하다. 정말 위상정렬 개념만 구현하면 풀리는 문제이다.

📍 collections.defaultdict()

graph = collections.defaultdict(list)

빈 배열을 만들 필요 없이, collections.defaultdict()를 이용한다. graph[a].append(b)에서 만약 a가 key로 없었다 해도 오류가 나지 않아서 편하다.

📃 소스코드

import sys
import collections
input = sys.stdin.readline

n, m = map(int, input().split())
graph = collections.defaultdict(list)
indegree = [0] * (n + 1) # 진입 차수 테이블

result = []
Q = collections.deque()

for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    indegree[b] += 1 # 진입 차수 증가
    
# 초기에 진입 차수 0인 노드들 큐에 삽입
for i in range(1, n + 1):
    if indegree[i] == 0:
        Q.append(i)
            
while Q:
    node = Q.popleft()
        # 꺼낸 원소는 위상 정렬 값에 append
    result.append(node)
        # 꺼낸 노드와 연결된 노드들 탐색
    for v in graph[node]:
        # node 제거 -> 연결된 노드들 간선 -1
        indegree[v] -= 1 
        # 진입간선 0인 노드들 큐에 추가
        if indegree[v] == 0:
            Q.append(v)

print(' '.join(map(str, result)))

카카오페이로 커피사기 ❤️ 토스,계좌로 커피사기 ❤️