[백준] 2252번 : 줄 세우기 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

2252번: 줄 세우기

 

1. 문제 설명

2. 풀이과정

해당 문제는 학생들을 노드로 생각하고, 키 순서 비교 데이터로 에지를 만든다고 생각했을 때 노드의 순서를 도출하는 가장 기본적인 문제이다.

답이 여러 개일 때 아무것이나 출력해도 된다는 전제는 위상 정렬의 결괏값이 항상 유일하지 않다는 알고리즘의 전제와 동일하다는 것을 알 수 있다.

 

위상 정렬(topology sort) : 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘

위상 정렬에서는 항상 유일한 값으로 정렬되지 않는다.

또한 사이클이 존재하면 노드 간의 순서를 명확하게 정의할 수 없으므로 위상 정렬을 적용할 수 없다.

 

위상 정렬의 수행 과정

1. 진입 차수(in-degree) : 자기 자신을 가리키는 에지의 개수
   • 2차원 리스트로 그래프를 표현
   • 가리키고 있는 값의 위치를  진입 차수 리스트에서 1만큼 증가시킴
2. 진입 차수 리스트에서 진입 차수가 0인 노드를 선택하고 선택된 노드를 정렬 리스트에 저장
3. 인접 리스트에서 선택된 노드가 가리키는 노드들의 진입 차수를 1씩 뺌
   • 진입 차수가 0인 노드를 선택하여, 해당 노드와 연결된 노드의 진입 차수를 1씩 뺌
   • 계속해서 진입 차수가 0인 노드를 선택하여 반복
   • 모든 노드가 정렬될 때까지 반복

 

인접 리스트에 노드 데이터를 저장하고, 진입 차수 배열값을 업데이트한다.

위상 정렬을 수행한다.

1. 진입 차수가 0인 노드를 큐에 저장
2. 큐에서 데이터를 뽑아와서 해당 노드를 탐색 결과에 추가하고, 해당 노드가 가리키는 노드의 진입 차수를 1씩 감소
3. 감소했을 때 진입 차수가 0이 되는 노드를 큐에 삽입
4. 큐가 빌 때까지 반복

슈도코드

1. N(학생 수), M(비교 횟수) 입력받기
2. graph(비교 데이터 저장 인접 리스트)
3. li(진입 차수 리스트)
4. for M만큼 반복:
   1. A, B (키를 비교한 두 학생의 번호) 입력받기
   2. 인접 리스트 데이터 저장
   3. 진입 차수 리스트 초기 데이터 저장
5. queue(큐 생성)
6. for N만큼 반복:
   1. if (진입 차수 리스트의 값이 0이면): 학생(노드)을 큐에 삽입
7. while (큐가 빌 때까지):
   1. node(현재 노드) = 큐에서 데이터 가져오기
   2. 현재 노드값 출력
   3. for 현재 노드에서 갈 수 있는 노드의 개수:
      1. 타깃 노드 진입 차수 리스트 값 1 감소
      2. if (타깃 노드의 진입 차수가 0이면): 큐에 타깃 노드 추가

반응형

3. 소스코드

import sys
from collections import deque

N, M = map(int, sys.stdin.readline().split())

graph = list([] for _ in range(N + 1))
li = [0] * (N + 1)
for _ in range(M):
    A, B = map(int, sys.stdin.readline().split())
    graph[A].append(B)
    li[B] += 1

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

while (queue):
    node = queue.popleft()
    print(node, end=' ')
    
    for i in graph[node]:
        li[i] -= 1
        if (li[i] == 0):
            queue.append(i)