🔍 Problem

백준 2252 줄 세우기

---

🤔 배경지식

가. 위상이란?

일단 먼저 위상정렬에서 “위상”이 가지는 의미를 알아보자. 위상이란 “어떤 사물이 다른 사물과의 관계 속에서 가지는 위치나 상태”를 의미한다. 즉 위상은 물체 사이의 관계를 의미하고 위상정렬에서는 이 관계가 “어떤 물체의 선행”이라는 의미로 표현된다. 예를들어 A와 B가 있고 A는 항상 B 앞에 나와야한다고 가정한다면 이는A는 B앞에 있어야되는 관계에 있다라고 표현할 수 있고 이는 다시 A는 B앞에 있어야하는 위상에 있다.라고 말할 수 있다는 것이다. 이러한 의미에서 “위상 정렬”은 두 물체 사이의 상관관계가 존재하는 정렬 문제에 풀 수 있다고 추측할 수 있다.

나. 위상 정렬

그렇다면 위상 정렬이란 무엇일까? 바로 아래 그림과 같은 상황이다.

여기서 올바른 순서는 무엇일까?

• 자료구조 → 알고리즘 → 고급 알고리즘

일 것이다. 그렇다 위에서 말했듯이 자료구조와 알고리즘 사이의 상관관계가 존재하는 것이고. 알고리즘과 고급 알고리즘에서도 상관관계가 존재한다. 이것을 그렇다면 어떻게 풀 것인가를 생각해보자.

다. 진입차수와 진출차수

• 진입차수(Indegree): 특정한 노드로 들어오는 간선의 개수
• 진출차수(Outdegree): 특정한 노드에서 나가는 간선의 개수 (여기서는 사용하지 않는다.)

우리는 위의사진에서 진입차수를 사용할 것이다. 진입차수가 낮은 노드부터 방문할 것이다. 하지만 진입차수가 동일한 경우도 있을 것이다. 이를 해결하기 위해 큐를 사용하여 다음과 같은 알고리즘을 사용할 것이다.

라. 큐를 사용한 알고리즘

1. 진입차수가 0인 모든 노드를 큐에 넣는다.
2. 큐가 빌 때까지 다음 과정을 반복한다.
	2.1 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거한다.
	2.2 새롭게 진입차수가 0이 된 노드를 큐에 넣는다.

위를 보면 처음에 진입차수가 0인 노드를 큐에 넣고 큐가 빌때까지 빼고 진입차수0 인 노드를 넣고 반복한다.

빼지넣

• 빼 : 큐에서 빼고
• 지 : 뺀 노드와 연결된 간선 지우고
• 넣 : 진입차수가 0인 노드를 넣는다.

---

💻 사고과정

1. 먼저 간선정보 리스트를 생성한다. 2차원이고 예를들어 1번째노드에 3,4 번이 연결되어 있으면[[], [3,4] … ] 이런 형식이다.
2. 두번째로 진입차수 정보 리스트를 선언한다. 예를들어 1번째 노드에 진입차수가 3이면 [0,3,...]이다.
3. 그리고 for문으로 a,b를 받아주고 a는 graph의 연결정보 예를들어 1,2면 graph[1].append(2) → 첫번째 노드에는 2라는 숫자를 넣어 2와 연결되어 있다를 표시해준다.
4. 그리고 진입차수 리스트의 2부분에 진입차수를 +1 해준다.
5. 일단 진입차수 0인 부분을 먼저 넣는다.
6. 빼지넣
   1. 먼저 큐에서 하나 뺀다. 그리고 result에 추가한다.
   2. 그리고 그 뺀 노드와 연결된 간선들을 없애준다. 즉 연결된 노드의 진입차수를 -1 해준다.
   3. 그리고 진입 차수들을 -1을 한 노드들 중!!!, 진입차수가 0이 존재하면 큐에 넣는다.
      1. 이 과정을 통해 진입차수가 0인 노드들을 순차 탐색을 할 필요가 없어진다. 진입차수가 -1이 된 노드들의 진입차수를 바로 0인지 검사해서 넣어주는 빼지넣 부분의 넣 부분을 지(지우기)에서 지운 노드들에서 체크하여 바로 넣어주는 것을 잊지말자! (넣와 지는 하나!)

---

🧑‍💻 전체 코드

import sys
from collections import deque

N,M=map(int,sys.stdin.readline().split())

graph=[[] for _ in range(N+1)]
entryCnt=[0]*(N+1)

for _ in range(M):
    a,b = map(int,sys.stdin.readline().split())
    graph[a].append(b)
    entryCnt[b]+=1
    
result=[]
que=deque()

# 초기넣
for i in range(1,N+1):
    if entryCnt[i] == 0:
        que.append(i)
        
# 빼지넣
while que:
        
    # 빼고
    node = que.popleft()
    result.append(node)
    
    #지우고
    for i in graph[node]:
        entryCnt[i]-=1
        #넣고 -> graph 리스트를 통해 해당 노드와 연결된 노드들만 진입차수 0인지 확인 가능!
        if entryCnt[i]==0:
            que.append(i)

print(*result)

---

😊 느낀점

위상정렬을 할 때, “빼지넣”만 기억하면 된다는 점과 지넣은 하나라는 것을 까먹으면 안된다는 것을 느꼈다. 빼지은는 빼고 지우고 넣고이고 지넣이 하나라는 것은 큐에서 뺀 노드와 연결된 노드의 진입차수를 -1 할 때(간선을 지울때), 그 진입차수를 -1한 노드를 0인지 체크하여 큐에 넣는다는 것이다. 이렇게 하므로서 바로바로 간선지우고 지운 간선과 연결된 노드들만 진입차수가 0인지 체크하므로 순차탐색으로 모든 노드의 진입차수가 0인지 확인할 필요가 없어진다!