백준 2252

<줄 세우기>

난이도 : 골드 3
1. 백준 문제
2252

2. 코드 알고리즘

3. 코드

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

import sys
input = sys.stdin.readline

n ,m = map(int, input().split())

# 인접 리스트 A
A = [[]for i in range(n+1)]

# 진입 차수 리스트
indegree = [0]*(n+1)

for i in range(m):
    # 인접리스트 데이터 저장
    v, e = map(int, input().split()) #v > e이므로 v가 e를 가르키게 해야됨(v가 먼저 오도록)
    A[v].append(e) #v가 e를 가르키면 인접리스트에선 A[v]에 e가 오게 됨
    indegree[e] += 1 # 진입 차수 리스트 초기 데이터 저장
    #가르킴 받은 요소의 진입차수 리스트 증가 (*진입차수 : 자기자신을 가리키는 에지 수)

#print("A:",A)
#print("indegree: ",indegree)

#위상 정렬 수행

#큐 생성
from collections import deque
queue = deque()

for i in range(1, n+1):
    if indegree[i] == 0:
        #print("indegree: ",i)
        queue.append(i)
        #break #?? 시작 노드를 찾으면 멈춰야 되지 않나요? §걸리는 부분
        # 구현한 위상 정렬 알고리즘 한계, 일단 0인 것들 다 넣어놓기
        # 아래 while문에서 중간에 멈추지 않도록
        # 부족한 부분?

#print("queue:",queue)

#큐가 빌때 까지 위상 정렬 수행
while queue:
    now_node = queue.pop()
    print(now_node, end=" ")
    for i in A[now_node]:
        indegree[i] -= 1
        if indegree[i] == 0:
            queue.append(i)

4. 코드 후기

• 실수한 부분(계속 막혔던 부분)
  queue에 인덱스를 넣어야 되는데 계속 indegree[i]를 넣고 있었다... 그럼 계속 0만 들어가서 당연히 안되는데...
  어떤 리스트에 무엇을 넣어야 하는지 주의하며, 인식하며 작성하자!

• 부족한 부분?
  처음에 queue에 진입차수가 0인 요소들을 한번에 다 넣는데 이게 위상정렬의 정의를 따르지 않는다. 물론 다양한 순서를 도출할 수 있는 것이 위상정렬 이지만 그렇다고 해서 진입차수가 0인 요소를 다 넣어놓고 실행하는 건 이미 답을 규정해놓는 알고리즘이랄까...
  -> 큐에 진입차수가 0인 a 요소를 넣은 다음! a요소의 인접리스트를 우선으로 시행 한 후! 진입차수가 0인 다른 요소를 넣어야 된다고 생각