[BOJ] #2252 줄 세우기 (Python)

🌱 문제

2252번: 줄 세우기

 

🌱 풀이

0. 입력 받기

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

for i in range(m):
    small, big = map(int, input().split())
    graph[small].append(big)
    in_degree[big] += 1

• 학생수(n)과 키를 비교한 횟수(m)을 입력받습니다.
• graph에 연결 정보를 저장합니다. (키가 작은 학생 번호에 키가 큰 학생 번호를 추가합니다.)
• 위상 정렬 방법을 사용하기 위해 진입 차수를 저장하기 위한 in_degree 리스트에 연결된 키가 큰 학생의 번호의 진입차수를 1 증가 시킵니다.

위상정렬

1. 진입 차수가 0인 노드 꺼내기

queue = deque()
for i in range(1, len(graph)):
    if in_degree[i] == 0:
        queue.append(i)

while queue:
    v = queue.popleft()
    print(v, end = ' ')
    for i in graph[v]:
        in_degree[i] -= 1
        if in_degree[i] == 0:
            queue.append(i)

• queue를 만들고, 진입 차수가 0인 학생 번호를 queue에 넣습니다.
• queue에서 학생을 하나씩 꺼내면서 꺼낸 학생과 연결된 학생의 진입 차수를 1씩 감소시킵니다.
• 감소시킨 진입 차수가 0이 되면 queue에 넣습니다.
• queue에 남은 학생이 없을 때까지 넣고 꺼내기를 반복합니다.

 

🌱 코드

import sys
from collections import deque
from collections import defaultdict

input = sys.stdin.readline

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

for i in range(m):
    small, big = map(int, input().split())
    graph[small].append(big)
    in_degree[big] += 1

queue = deque()
for i in range(1, len(graph)):
    if in_degree[i] == 0:
        queue.append(i)

while queue:
    v = queue.popleft()
    print(v, end = ' ')
    for i in graph[v]:
        in_degree[i] -= 1
        if in_degree[i] == 0:
            queue.append(i)