[백준/파이썬(Python)] 2252 줄세우기(Gold 3)

💜문제

---

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

2252번: 줄 세우기

 

💜코드

---

from collections import deque
n,m=map(int,input().split())
num=[[] for _ in range(n+1)]
visit=[0]*(n+1)
for _ in range(m):
    a,b=map(int,input().split())
    num[a].append(b)
    visit[b]+=1

def topologySort():
    res=[]
    q=deque()

    for i in range(1,n+1):
        if visit[i]==0:
            q.append(i)
    while q:
        now=q.popleft()
        res.append(now)
        for i in num[now]:
            visit[i]-=1
            if visit[i]==0:
                q.append(i)
    print(*res)
topologySort()

 

💜풀이

---

위상정렬을 이용해야 한다.

A번 학생이 B 학생보다 반드시 먼저 앞에 오는 상황이 주어진다. 그래서 A→B를 만족시키며 정렬을 해야하므로 위상정렬을 이용하면 된다.

 

위상정렬의 과정

1. 진입차수가 0인 정점을 큐에 삽입
2. 큐에서 원소를 꺼내 해당 원소와 연결된 간선을 모두 제거
3. 제거한 후에 진입차수가 0인 정점을 큐에 삽입
4. 이후 2~3 과정 반복

 

먼저 진입차수가 0인 번호를 큐에 넣고, 큐에서 먼저 꺼내 해당 번호에 연결된 간선들을 제거한다.

여기서 진입차수란, 예를 들어 1번 학생→2번 학생, 즉 1번이 2번보다 앞에 있는 상황에서 1번보다 먼저 앞에 있는 사람은 없으니 진입차수는 0이다. 2번은 2번보다 앞에 있는 학생이 1번 1명이 있으니까 진입차수가 1이 된다.

다시 말해 진입차수는 해당 번호를 탐색하기 위해 먼저 선행되어야 하는 번호의 갯수라고 보면 된다.

그래서 학생들을 입력받을 때 b앞에 a가 있어야 하기 때문에 b의 진입차수를 1 증가시킨다.

그리고 루프를 돌면서 진입차수가 0인 번호를 큐에 넣고, 큐에서 먼저 꺼내 해당 번호에 연결된 간선들을 제거한다.

간선들을 제거하면서 현재 탐색하고 있는 번호를 결과 리스트에 넣는다.

그리고 해당 번호를 진입차수로 가지고 있는 진입차수를 1씩 뺀다.

뺏을 때 진입차수가 0이라면 큐에 넣는다.