[알고리즘][Python] 백준(BOJ) 2252 줄 세우기_파이썬

 

2252 줄 세우기    www.acmicpc.net/problem/2252

2252번: 줄 세우기

 

 

 

 

 

문제 풀기 전 공부할 것 : 그래프 이론, 위상 정렬

 

 

 

 

 

 

 

풀이 1

<내용>

• 키를 비교한 두 학생의 번호 A, B를 입력받고 heights에 A 다음에 B가 와야 한다는 것을 저장하고 students에 B 앞에 A가 와야 하므로 +1을 한다.
• students의 값이 0인 곳은 앞에 와야 하는 학생이 없으므로 먼저 줄을 세운다.
• i 학생을 줄을 세우면 i 학생 다음에 와야 하는 학생들을 heights를 통해 탐색하고 students에서 -1을 한다.
• 위의 두 과정을 반복하여 줄을 세운 결과를 출력한다.

 

 

<코드>

from collections import deque

n, m = map(int, input().split())
students = [0 for _ in range(n)]
heights = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    students[b-1] += 1
    heights[a-1].append(b-1)
    
que = deque()
for i in range(n):
    if students[i] == 0:
        que.append(i)
        
res = []
while que:
    i = que.popleft()
    res.append(i+1)
    for j in heights[i]:
        students[j] -= 1
        if students[j] == 0:
            que.append(j)
print(*res)

 

 

 

 

 

 

 

 

 

풀이 2

<내용>

• heights를 리스트가 아닌 dictionary로 표현했다.
• 위의 과정과 똑같이 진행한다.

 

 

<코드>

from collections import deque

n, m = map(int, input().split())
students = [0 for _ in range(n)]
heights = {}
for _ in range(m):
    a, b = map(int, input().split())
    students[b-1] += 1
    if a-1 in heights:
        heights[a-1].append(b-1)
    else:
        heights[a-1] = [b-1]
    
que = deque()
for i in range(n):
    if students[i] == 0:
        que.append(i)
        
res = []
while que:
    i = que.popleft()
    res.append(i+1)
    if i in heights:
        for j in heights[i]:
            students[j] -= 1
            if students[j] == 0:
                que.append(j)
                
print(*res)