[백준] 줄 세우기 (Python 파이썬 풀이)
Problem Point
학생들간의 순서를 보여주고 줄을 세우는 경우의 수를 말한다. 이렇듯 순서를 중요시 여기는 문제에서는 위상정렬을 떠올리면 풀이시간을 줄일 수 있다.
문제출저 : https://www.acmicpc.net/problem/2252
문제에서 요구하는 값들을 받고 간선을 받아서 딕셔너리 형태로 저장한다. 또 한 위상을 알기 위해서 따로 리스트로 저장하기 위해 degree 리스트를 선언하였다.
덱을 선언하여 전에 입력받은 순서대로 위상을 확인하도록 하였다. 그 후 각 연결된 노드를 순회하며 위상을 감소시키며 결과값을 도출한다.
최종풀이
from collections import deque, defaultdict
M,N=map(int,input().split())
queue=deque()
key= defaultdict(lambda: [])
degree=[0 for i in range(M+1)]
answer=[]
for i in range(N):
a ,b =map(int,input().split())
key[a].append(b)
degree[b]+=1
for i in range(1,M+1):
if degree[i]==0:
queue.append(i)
while queue:
start=queue.popleft()
answer.append(start)
for i in key[start]:
degree[i]-=1
if degree[i]==0:
queue.append(i)
print(*answer)
Author And Source
이 문제에 관하여([백준] 줄 세우기 (Python 파이썬 풀이)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@denhur62/백준-줄-세우기-Python-파이썬-풀이저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)