# 2252번 - 줄 세우기

- Author: @mildsalmon
- Published: 2022-01-25
- Updated: 2022-01-25
- Source: http://blex.me/@mildsalmon/2252%EB%B2%88-%EC%A4%84-%EC%84%B8%EC%9A%B0%EA%B8%B0
- Tags: 파이썬, 알고리즘, 코딩테스트, 문제, bfs, 위상정렬, 백준, dag

---

# 1. 줄 세우기

- 난이도
	- 골드 3
- 시간 제한
	- 2초
- 메모리 제한
	- 128 MB
- 출처
	- [2252번: 줄 세우기 (acmicpc.net)](https://www.acmicpc.net/problem/2252)

### A. 📜 문제

위 백준 사이트에 접속하여 문제를 확인해주세요.
	
### B. 💡 내 답안

##### a. 😅 😊 1차 시도 (성공)

```python
import sys
from collections import deque

input = sys.stdin.readline


def topology_sort(indegree: list) -> list:
    global lines

    q = deque()

    '''
    enumerate로 q에 student를 삽입하면, 0번째 인덱스가 반드시 들어가는 비효율적인 구조가 되어서, range로 변경함.
    '''
    # for i, value in enumerate(indegree):
    for i in range(1, len(indegree)):
        if indegree[i] == 0:
            q.append(i)

    answer = []

    while q:
        student = q.popleft()
        answer.append(student)

        for next_student in lines[student]:
            indegree[next_student] -= 1

            if indegree[next_student] == 0:
                q.append(next_student)

    return answer[::-1]


if __name__ == "__main__":
    n, m = list(map(int, input().split()))
    lines = [[] for _ in range(n+1)]
    indegree = [0 for _ in range(n+1)]

    for _ in range(m):
        A, B = list(map(int, input().split()))
        lines[B].append(A)
        indegree[A] += 1

    print(*topology_sort(indegree))

```

##### a. 🙄 회고

> 내 풀이

- 어제 [[빅데이터를 지탱하는 기술]]을 공부하며 봤던 DAG가 떠올랐다. DAG에서 우선순위를 표현하기 위해 위상 정렬을 이용한다고 알고있었는데, 그렇게 생각하니까 위상 정렬이 더 쉬워졌다.

### C. 🧐 문제 해설

> 이해한 내용을 바탕으로 작성했습니다.

```
예제 1

3 2
1 3
2 3
```

여기에서 A 학생은 B 학생 앞에 위치해야한다.  
따라서, 정답은 `1 2 3`, `2 1 3`이 될 수 있다.

위상 정렬은 진입 차수를 따로 관리해야한다.  
A, B 순서로 진행이 된다면, A의 진입 차수는 1, B의 진입 차수는 0이다.  
그럼 진입 차수가 0인 노드들을 ready queue에 집어넣고 진행시킨다.  

보통 위상 정렬은 이정도로 끝나는 듯 하다.  
좀 더 깊이 들어가면, 병렬적으로 처리되는 작업들을 언제까지 기다릴지도 생각해야겠지만, 그런건 빅데이터를 좀 더 공부해보고 생각해야겠다.

---

비슷한 위상 정렬 문제는 아래 링크를 통해 확인할 수 있다.

- [Chap 18. 그래프이론 - Q45. 최종 순위 — mildsalmon (blex.me)](https://blex.me/@mildsalmon/chap-18-%EA%B7%B8%EB%9E%98%ED%94%84%EC%9D%B4%EB%A1%A0-q45-%EC%B5%9C%EC%A2%85-%EC%88%9C%EC%9C%84)


# 참고문헌

[baekjoon](https://www.acmicpc.net/user/baekjoon). [2252번: 줄 세우기 (acmicpc.net)](https://www.acmicpc.net/problem/2252). Baekjoon. (accessed Jan 25, 2022)