[백준(BOJ)] 2252번 : 줄 세우기 - PYTHON[파이썬]

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

2252번: 줄 세우기

 

---

⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

• 그래프 이론
• 위상 정렬

 

---

 

⊙ 문제 접근 과정

 

위상 정렬 알고리즘 문제다.

 

위상 정렬 알고리즘은 큐를 이용하여 풀 수 있다.

 

큐를 이용하여 위상 정렬 알고리즘을 푸는 과정은

 

1️⃣ 진입 차수가 0인 모든 노드를 큐에 넣는다.

2️⃣ 큐가 빌 때까지 while문을 돌린다!!

3️⃣ 반복문에서는 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거

4️⃣ 새롭게 진입 차수가 0이 된 노드를 큐에 추가

 

 

위상 정렬에서는 여러 가지 답이 존재할 수도 있다.

스택을 활용하여 풀어주자

 

---

 

⊙ 문제 풀이

 

import sys
from collections import deque

input = sys.stdin.readline

N, M = map(int, input().split())
graph = [[] for _ in range(N+1)]
indegree = [0] * (N+1)

for _ in range(M):
    x, y = map(int, input().split())
    graph[x].append(y)
    indegree[y]+=1

# 위상 정렬
def topo():
    result = []
    q = deque()

    for i in range(1,N+1):
        if indegree[i]==0:
            q.append(i)

    while q:
        a = q.popleft()
        result.append(a)

        for i in graph[a]:
            indegree[i]-=1

            if indegree[i]==0:
                q.append(i)
    for i in result:
        print(i,end=' ')

topo()

 

---

⊙ 결과

 

---

⊙ 마무리

 

 

NONE

 

 

좋아요는 로그인하지 않아도 누를 수 있습니다!