[백준] 2252 줄 세우기

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 이해 및 접근

학생들의 절대적인 키가 아닌 상대적인 키를 입력으로 받고 있습니다.

이러한 경우 한 학생을 기준으로 그 학생보다 크거나 작은 학생들의 목록만 알아낼 수 있습니다.

 

위상 정렬 알고리즘을 이용하여, 한 학생보다 키가 작은 모든 학생들을 줄을 세우고나면 해당 학생을 줄을 세우는 방식으로 접근하였습니다.

2) 알고리즘

• 위상 정렬

3) 풀이 코드

사용 언어 - Python

import sys
from collections import deque
sys.stdin = open('input.txt')

N, M = map(int, sys.stdin.readline().split())           # 학생의 수, 키를 비교한 횟수
linked = [[] for _ in range(N+1)]                       # 각 학생들의 본인보다 키 큰 학생의 목록
need = [0] * (N+1)                                      # 각 학생들의 본인보다 키 작은 학생의 수
answer = []                                             # 정답

for _ in range(M):
    a, b = map(int, sys.stdin.readline().split())       
    linked[a].append(b)                                 # 키 작은 학생 기준, 키 큰 학생 이름 기록
    need[b] += 1                                        # 키 큰 학생 기준으로 키 작은 학생 수 추가

q = deque()                             # 줄 서야하는 명단     
for i in range(1, N+1):
    if not need[i]:                     # 학생들을 한번씩 확인하여 키가 작아서
        q.append(i)                     # 가장 앞에 나와야 하는 모든 학생들 추가

while q:                                # 학생들이 아직 줄을 서지 않았다면
    node = q.popleft()

    for next in linked[node]:           # 현재 학생보다 키가 큰 학생들은
        need[next] -= 1                 # 키 작은 학생의 수 하나씩 뺌
        if need[next] <= 0:             # 키 큰 학생의 앞에 있는 키 작은 학생들이 모두 줄을 섰으면 줄서는 명단에 추가
            q.append(next)
    
    answer.append(node)                 # 현재 학생 줄 세우기

print(*answer)

---

📝 결과 및 학습한 내용

1) 어려웠던 내용

특별히 없습니다.

2) 새롭게 학습한 내용

특별히 없습니다.

---

🔗 문제 링크

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

2252번: 줄 세우기

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다