[BOJ] 2252번 줄 세우기 / 사용언어 : 파이썬(python)

※ 문제링크

2252번: 줄 세우기

※ 관련개념

[알고리즘] 위상 정렬(Topological Sort)이란 - Heee's Development Blog

해당 문제는 위상정렬 알고리즘의 대표적인 문제로 해당 알고리즘에 대한 기본적인 이해를 했으면 쉽게 해결할 수 있는 문제였다. 위상정렬을 간단하게 설명하면 들어오는 간선수를 확인하여 정렬을 하는 알고리즘으로 쉽게 잘 설명해놓은 사이트 링크를 걸어 두었으니 해당 사이트에서 개념확인 후 문제를 해결하면 좋을 것 같다. 해당 문제를 푸는데 어려웠던 점은 백준 사이트에서 주어진 예제의 답과 다른 답이 나오는 경우가 빈번하여 제대로 알고리즘이 구현되었는지 확인하기가 까다롭다는 점인데, 기본 위상정렬에서 크게 변형된 부분은 없으니 예제의 답과 다르게 나오더라도 걱정하지 않아도 될 것 같다. 자세한 풀이방법과 코드는 아래와 같다.

1. 입력받은 값들을 각각 변수에 할당해주고, 이어진 간선의 개수를 확인할 그래프와 각 정점에 대해 들어가는 간선의 수를 기록할 리스트를 작성해준다.

2. 처음 상태에서의 들어오는 간선의 개수가 0인 변수들을 확인하고 저장하기위해 반복문을 돌려 초기상태를 기록해준다.

3. while문을 활용하여 저장한 정점 리스트가 빌 때까지 반복문을 돌릴 수 있게 해주고, 간선의 갯수가 0인 정점을 하나씩 제거하고 상태를 갱신하가며 결과값을 작성해준다.

4. 반복문 종료 후 print문을 활용하여 결과값을 출력해준다.(시간 및 메모리 절감을 위해 sys를 활용하였습니다.)

 

from collections import deque
import sys

# input = sys.stdin.readline
N, M = map(int, input().split())
graph = [[] for _ in range(N+1)]
link = [0 for _ in range(N+1)]
for _ in range(M):
    start, end = map(int, input().split())
    graph[start].append(end)
    link[end] += 1

ans = []
queue = deque()
for i in range(1, N+1):
    if link[i] == 0:
        queue.append(i)
        link[i] = -1

while queue:
    cp = queue.popleft()
    ans.append(cp)
    for number in graph[cp]:
        link[number] -= 1
        if link[number] == 0:
            queue.append(number)
print(*ans)

 

P.S 더 나은 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.