알고리즘 - Python / 백준 - 2252번 : 줄 세우기

2252번: 줄 세우기 (acmicpc.net)

2252번: 줄 세우기

 

---

풀이

• 줄을 세울 때 , 어떤 사람이 어떤 사람 앞에 있어야 한다는 조건들을 가지고 줄을 세울 수 있는 경우를 출력하면 되는 문제다.
• 만약 4 2의 경우 4번 사람이 2번 사람 앞에 서야 한다는 이야기이다.
• 모든 조건을 배열에 저장하고 큐를 이용해 위상 정렬을 구현하였다.
• 1. 모든 노드를 검사해 그 노드의 진입 차수가 0이 라면 큐에 추가한다. ( 노드 간 간선 정보 , 노드별 진입 차수 배열 존재 )
• 2. 이후 큐를 pop 하면서 pop 된 요소를 정답 배열에 추가한다.
• 3. 큐에서 빼낸 요소(노드)가 가리키는 간선을 뜯어낸다. ( 해당 노드가 가리키는 노드들의 진입 차수를 줄임 )
• 4. 이후 다시 진입차수가 0인 노드들을 큐에 추가한다.
• 5. 1번 ~ 4번 까지의 과정을 모든 노드를 방문할 때까지 반복한다.
• 5-1. 만약 그래프가 2개 이상으로 나뉘어져 있거나 , 어느 그래프에도 속하지 않았더라도 문제없다. 위상 정렬은 진입 차수를 통해서 이루어지기 때문에 해당 경우들도 모두 정답 배열에 추가된다.

 

 

import sys
n,m = map(int , sys.stdin.readline().split(" "))
s = [[] for t in range(n+1)]
check = [0 for t in range(n+1)]
for _ in range(m):
    a, b = map(int, sys.stdin.readline().split(" "))
    s[a].append(b)
    check[b] += 1

start = []
ans = []
visited = [0 for t in range(n+1)]

for i in range(1,len(check)):
    if check[i] == 0:
        start.append(i)
        visited[i] = 1


while len(start) != 0:
    k = start.pop(0)
    visited[k] = 1
    ans.append(k)
    for p in s[k]:
        check[p] -= 1
    for o in range(1,len(check)):
        if check[o] == 0 and visited[o] == 0:
            start.append(o)
            visited[o] = 1

for i in range(0,len(ans)-1):
    print(ans[i], end=" ")
print(ans[len(ans)-1])

---