[백준] 2252 줄세우기 (python 파이썬)

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

2252번: 줄 세우기

 

풀이 과정

입력값은 키를 비교한 학생 A와 B의 순서가 M개만큼 주어진다. 

바로 이전에 풀었던 ACMCraft와 비슷한 유형인 거 같아 같은 방법으로 해결했다.

위상 정렬만 알면 간단하게 해결 가능하다.

from collections import deque
import sys
input = sys.stdin.readline
N, M = map(int,input().rstrip().split())

student_adj_list = [[] for _ in range(N + 1)]
in_degree = [0 for _ in range(N + 1)]
que = deque()

for i in range(M):
    x, y = map(int,input().rstrip().split())
    student_adj_list[x].append(y)
    in_degree[y] += 1

정점에 들어오는 간선수를 저장하기 위해 in_degree리스트와 인접 리스트 student_adj_list를 선언한다.

이후 들어오는 M개의 입력값을 저장하면 준비 끝

 

for i in range(1,N + 1):
    if in_degree[i] == 0:
        que.append(i)

while que:
    node = que.popleft()
    print(node,end=' ')
    for student in student_adj_list[node]:
        in_degree[student] -= 1
        if in_degree[student] == 0:
            que.append(student)
print()

가장 초기 상태에 정점에 들어오는 간선수(in_degree) 값이 0인 것들을 큐에 넣어준다.

해당 정점과 연결된 정점들의 in_degree값들을 1씩 감소시켜준다.

값이 0이 된 정점은 큐에 넣어준다. 큐가 비워질 때까지 반복하면 된다.

 

전체 코드

from collections import deque
import sys
input = sys.stdin.readline
N, M = map(int,input().rstrip().split())

student_adj_list = [[] for _ in range(N + 1)]
in_degree = [0 for _ in range(N + 1)]
que = deque()

for i in range(M):
    x, y = map(int,input().rstrip().split())
    student_adj_list[x].append(y)
    in_degree[y] += 1

for i in range(1,N + 1):
    if in_degree[i] == 0:
        que.append(i)

while que:
    node = que.popleft()
    print(node,end=' ')
    for student in student_adj_list[node]:
        in_degree[student] -= 1
        if in_degree[student] == 0:
            que.append(student)
print()