[Python][백준] 2252. 줄 세우기 / 위상정렬, DAG (G3)

🔗링크 :  

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

---

✨ 위상정렬 풀이 방식

위상 정렬은 DAG(Directed Acyclic Graph)의 조건을 만족하면서 모든 노드를 나열하는 정렬 방법이다. 

여기에서 DAG라는 말이 좀 어렵게 느껴질 수 있지만, 쉽게 말해 비순환형 그래프로 반드시 사이클이 없어야 한다. 

(뭐 어렵게 생각할 필요없고, 아래 예시와 같이 비순환형 그래프를 DAG라 보면 된다.)

 

위상정렬 같은 경우 그래프의 구조와 노드의 연결 방식에 따라 여러개의 답이 나올 수 있다. 

 

EX)

다음은 위상 정렬에 대한 간단한 예시이다.

아래의 그래프를 위상정렬로 나열하면 되는 것이다.  

풀이과정은 다음과 같다.

1. 그래프 및 진입 차수 계산
2. 진입 차수 0인 노드 큐에 추가
3. 큐에서 노드 꺼내기
4. 결과 출력 

→ 위상정렬 말이 어려워 보이는데, 간단하다 ... 

 

위상정렬에 대한 개념이 이해됐으면, 이제 실제로 문제를 풀어보자 !

---

🗒️파이썬 코드 풀이

from collections import deque

N,M = map(int,input().split())

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

for _ in range(M):
  a,b = map(int,input().split())
  graph[a].append(b)
  graph_count[b] += 1
  
q = deque()
for i in range(1,N+1):
  if graph_count[i] == 0 :
    q.append(i)

while q:
  v = q.popleft()
  print(v, end = " ")
  for i in graph[v]:
    graph_count[i] -= 1 
    if graph_count[i] == 0 :
      q.append(i)

 

1. 진입점들을 나타내줄 graph, 몇 개의 진입점을 가지고 있는지는 graph_count 로 변수를 만들어주었다. 

 

2. 첫번째로 모든 노드를 반복문으로 한번씩 탐색하면서, graph_count = 0 인 노드를 Queue에 넣어준다. 

 

3. 이제 Queue를 하나씩 pop 하면서, 해당 노드와 연결된 노드의 진입점 개수를 -1 해준다 . 

 

4. 만일 노드 진입점의 개수가 0인 경우는 Queue에 push 해준다.  

 

참고로 위상정렬은 그래프 구조에 따라 답이 좀 다르게 나올 수 있다 .

나의 풀이 같은 경우 예제 2의 출력과는 답이 다르다는 점 참고  !!

 

📌 문제 코멘트 

위상정렬, DAG 같은 말들이 낯설게 느껴져서, 맨 처음 접근에 두려움을 가졌다.

 

여태 여러 정렬들을 배워왔는데, 막상 쓰려면 막히고 어려울 것 같다는 생각이 있다. 

근데 이미 다 한번씩 정리했고, 그때에도 큰 어려움이 없었기 때문에 너무 어렵게 생각하지 말자 ! 

---

📚문제

N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다.

일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 횟수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이다.

학생들의 번호는 1번부터 N번이다.

출력

첫째 줄에 학생들을 앞에서부터 줄을 세운 결과를 출력한다. 답이 여러 가지인 경우에는 아무거나 출력한다.

예제 입력 1 복사

3 2
1 3
2 3

예제 출력 1 복사

1 2 3

예제 입력 2 복사

4 2
4 2
3 1

예제 출력 2 복사

4 2 3 1