[BOJ/python]2252

백준 2252 - 줄 세우기 파이썬 풀이 입니다

위상 정렬

위 문제는 순서가 정해져 있는 작업을 차례로 처리한다는 점에서
위상 정렬을 이용해서 풀이를 할 수 있다

• 위상 정렬은 사이클이 발생하지 않는다는 조건하에 수행할 수 있다

위와 같이 진입 차수를 구하여 위상정렬을 구현할 수 있는데 구현 순서는 다음과 같다

• 진입 차수를 구하고 queue를 초기화 할 때 진입 차수가 0인 노드를 넣는다
• 하나씩 queue에서 노드를 꺼내고, 연결 되어있는 다음 노드의 진입차수 에 각각 -1을 해준다(현재 노드-다음 노드의 간선 정보를 삭제하는 작업)
• 다음 노드의 진입차수가 0이 될 경우에 queue에 append 한다
• queue에서 pop 된 순서가 노드의 위상 정렬 순서이다

코드

from collections import deque 
from collections import defaultdict


def solution():
    N, M = map(int, input().split())

    queue = deque([])
    cnt = defaultdict(int)
    connect = defaultdict(list)

    for _ in range(M):
        A, B = map(int, input().split())
        cnt[B] += 1
        connect[A].append(B)

    for i in range(1, N + 1):
        if cnt[i] == 0:
            queue.append(i)
    
    answer = []

    while queue:
        node = queue.popleft()
        answer.append(node)

        for next in connect[node]:
            cnt[next] -= 1
            if cnt[next] == 0:
                queue.append(next)

    print(' '.join(map(str, answer)))

solution()

• 연결 정보(A -> B)를 입력받을 때 노드간의 연결 정보(connect)와 진입 차수(cnt)를 갱신한다
  • B의 경우 진입 차수 + 1을 해준다
  • A의 경우 다음 노드 정보들을 저장한다
• cnt가 0일 경우 queue에 노드 정보를 append 한다
• queue에서 값을 하나씩 꺼내고, 현재 노드를 answer list에 저장한다
• 다음 노드의 진입 차수에 -1을 해주고 진입 차수가 0이 되면 queue에 append한다
• answer 리스트를 문자열로 잘 출력한다

특이한 점은 이 문제는 답이 여러개가 될 수 있는데 크게 조건을 주지 않아 아무렇게나 출력해도 된다는 점이었다(개꿀~)

---

아싸 티어 상승
실버를 지나 골드를 넘어 언젠가 플레로 갈거야~