[백준] 2252 줄 세우기 (Python, 위상정렬)

🔗 문제 링크

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

💻 코드

from collections import deque, defaultdict

def topological_sort_bfs(n, edges):

    graph = defaultdict(list)
    indegree = [0] * n

    for u, v in edges:
        graph[u].append(v)
        indegree[v] += 1

    dq = deque([i for i in range(n) if indegree[i] == 0])
    result = []

    while dq:
        node = dq.popleft()
        result.append(node)
        for nxt in graph[node]:
            indegree[nxt] -= 1
            if indegree[nxt] == 0:
                dq.append(nxt)

    if len(result) != n:
        return []  # 사이클 존재
    return result


n,m  = map(int,input().split())
edges = []

for _ in range(m):
    a,b = map(int,input().split())
    edges.append((a-1,b-1))

result = topological_sort_bfs(n,edges)

print(*[x+1 for x in result])

🧩풀이

N명의 학생을 한 줄로 세우는데, 일부 학생들의 키를 비교한 결과가 주어진다. "A가 B 앞에 서야 한다"는 조건을 모두 만족하는 줄 세우기 순서를 구하는 문제이다.

🤔 왜 위상정렬인가?

이 문제는 부분적인 선후 관계가 주어지고, 이를 모두 만족하는 전체 순서를 구하는 문제이다.

"A가 B 앞에 서야 한다" → A → B 방향 간선으로 모델링
학생들 사이의 관계가 방향 비순환 그래프(DAG)를 형성
모든 간선의 방향을 만족하는 노드 순서를 구하는 것이 바로 위상정렬의 정의

단순 정렬(sort)로는 풀 수 없다. 키 값 같은 절대적 기준이 없고, 비교되지 않은 학생들 사이에는 순서가 자유롭기 때문이다.

💡 풀이 접근: BFS 기반 위상정렬 (Kahn's Algorithm)

핵심 아이디어

각 노드의 진입차수(indegree)를 구한다
진입차수가 0인 노드를 큐에 삽입
큐에서 노드를 꺼내며 결과에 추가하고, 연결된 노드의 진입차수를 1 감소
진입차수가 0이 된 노드를 다시 큐에 삽입
큐가 빌 때까지 반복

예시로 이해하기

이 입력은 다음과 같은 그래프를 만든다:

4 → 2
3 → 1

초기 진입차수: 1번(1), 2번(1), 3번(0), 4번(0)
진입차수 0인 노드: 3, 4 → 큐에 삽입
3을 꺼내면 1의 진입차수가 0이 되어 큐에 추가
4를 꺼내면 2의 진입차수가 0이 되어 큐에 추가
결과: 3 4 1 2 (답이 여러 개 가능)

두 그룹(4→2, 3→1)이 서로 독립적이므로, 조건만 만족하면 순서는 자유롭다.

🔍 코드 분석

입력 처리

python

n, m = map(int, input().split())
edges = []
for _ in range(m):
    a, b = map(int, input().split())
    edges.append((a - 1, b - 1))

문제에서 학생 번호는 1부터 N까지이지만, 함수 내부는 0부터 N-1을 기준으로 동작한다. 따라서 입력 시 a-1, b-1로 변환한다.

그래프 구성 및 진입차수 계산

python

graph = defaultdict(list)
indegree = [0] * n

for u, v in edges:
    graph[u].append(v)
    indegree[v] += 1

graph[u]: u에서 나가는 간선의 도착 노드 리스트
indegree[v]: v로 들어오는 간선의 수

BFS 위상정렬

python

dq = deque([i for i in range(n) if indegree[i] == 0])

진입차수가 0인 노드, 즉 앞에 와야 할 학생이 없는 학생부터 시작한다.

python

while dq:
    node = dq.popleft()
    result.append(node)
    for nxt in graph[node]:
        indegree[nxt] -= 1
        if indegree[nxt] == 0:
            dq.append(nxt)

노드를 꺼낼 때마다 연결된 노드의 진입차수를 줄이고, 0이 되면 큐에 추가한다.

사이클 감지

python

if len(result) != n:
    return []

모든 노드가 결과에 포함되지 않으면 사이클이 존재한다는 의미이다. (이 문제에서는 사이클이 없다고 보장됨)

출력

python

print(*[x + 1 for x in result])

0-indexed 결과를 다시 1-indexed로 변환하여 출력한다.

⏱ 시간복잡도

그래프 구성: O(M)
위상정렬: O(N + M)
전체: O(N + M)

N은 최대 32,000, M은 최대 100,000이므로 최대 약 132,000번의 연산으로 충분히 시간 안에 통과한다.

✨ 위상 정렬

사이클이 없는 방향 그래프(DAG)의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것을 의미
예) 선수 과목을 고려한 학습 순서 설정

위상 정렬 동작 예시 (큐)

진입 차수가 0인 모든 노드를 큐에 넣기
큐가 빌때까지 다음의 과정 반복
1. 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거
2. 새롭게 진입차수가 0이 된 노드를 큐에 넣기

위상 정렬의 특징

여러 가지 답이 존재할 수 있음
- 한 단계에서 큐에 새롭게 들어가는 원소가 2개이상인 경우가 있다면 여러가지 답이 존재
모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재
스택을 활용한 DFS를 이용해 위상정렬 수행 가능

위상 정렬 BFS 코드

from collections import deque, defaultdict 

def topological_sort_bfs(n, edges):
  """
  n: 노드수 (0~n-1)
  edges: [(u,v), ...] u->v 방향 간선 
  """
  
  graph = defaultdict(list)
  indegree = [0] * n 

  for u, v in edges:
    graph[u].append(v)
    indegree[v] += 1

  dq = deque([i for i in range(n) if indegree[i] == 0 ]_
  result = []

  while dq:
    node = dq.popleft()
    result.append(node)
    for next in graph[nodex]:
      indegree[next] -= 1:
      if indegree[next] == 0:
        dq.append(next)

  if len(result) != n: 
    return [] # 사이클 존재 
  return result

진입차수(indegree)가 0인 노드부터 큐에 넣고, 하나씩 꺼내며 연결된 노드의 진입차수를 하나씩 줄여가는 방식

위상정렬 DFS 코드

from collections import defaultdict

def topological_sort_dfs(n,edges):
  graph = defaultdict(list)
  for u,v in edges:
    graph[u].append(v)

  visited = [0] * n # 0 미방문 1 진행중 2완료
  result = [] 

  def dfs(node):
    if visited[node] == 1:
      return False
    if visited[node] == 2:
      return True 
    for next in graph[node]:
      if not dfs(next):
        return False 
    visited[node] = 2
    result.append(node)
    return True
 
for i in range(n):
  if visited[i] == 0:
    if not dfs(i):
      return []

  return result[::-1]

🔗 문제 링크

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

💻 코드

from collections import deque, defaultdict

def topological_sort_bfs(n, edges):

    graph = defaultdict(list)
    indegree = [0] * n

    for u, v in edges:
        graph[u].append(v)
        indegree[v] += 1

    dq = deque([i for i in range(n) if indegree[i] == 0])
    result = []

    while dq:
        node = dq.popleft()
        result.append(node)
        for nxt in graph[node]:
            indegree[nxt] -= 1
            if indegree[nxt] == 0:
                dq.append(nxt)

    if len(result) != n:
        return []  # 사이클 존재
    return result


n,m  = map(int,input().split())
edges = []

for _ in range(m):
    a,b = map(int,input().split())
    edges.append((a-1,b-1))

result = topological_sort_bfs(n,edges)

print(*[x+1 for x in result])

🧩풀이

🤔 왜 위상정렬인가?

이 문제는 부분적인 선후 관계가 주어지고, 이를 모두 만족하는 전체 순서를 구하는 문제이다.

"A가 B 앞에 서야 한다" → A → B 방향 간선으로 모델링
학생들 사이의 관계가 방향 비순환 그래프(DAG)를 형성
모든 간선의 방향을 만족하는 노드 순서를 구하는 것이 바로 위상정렬의 정의

단순 정렬(sort)로는 풀 수 없다. 키 값 같은 절대적 기준이 없고, 비교되지 않은 학생들 사이에는 순서가 자유롭기 때문이다.

💡 풀이 접근: BFS 기반 위상정렬 (Kahn's Algorithm)

핵심 아이디어

각 노드의 진입차수(indegree)를 구한다
진입차수가 0인 노드를 큐에 삽입
큐에서 노드를 꺼내며 결과에 추가하고, 연결된 노드의 진입차수를 1 감소
진입차수가 0이 된 노드를 다시 큐에 삽입
큐가 빌 때까지 반복

예시로 이해하기

이 입력은 다음과 같은 그래프를 만든다:

4 → 2
3 → 1

초기 진입차수: 1번(1), 2번(1), 3번(0), 4번(0)
진입차수 0인 노드: 3, 4 → 큐에 삽입
3을 꺼내면 1의 진입차수가 0이 되어 큐에 추가
4를 꺼내면 2의 진입차수가 0이 되어 큐에 추가
결과: 3 4 1 2 (답이 여러 개 가능)

두 그룹(4→2, 3→1)이 서로 독립적이므로, 조건만 만족하면 순서는 자유롭다.

🔍 코드 분석

입력 처리

python

n, m = map(int, input().split())
edges = []
for _ in range(m):
    a, b = map(int, input().split())
    edges.append((a - 1, b - 1))

문제에서 학생 번호는 1부터 N까지이지만, 함수 내부는 0부터 N-1을 기준으로 동작한다. 따라서 입력 시 a-1, b-1로 변환한다.

그래프 구성 및 진입차수 계산

python

graph = defaultdict(list)
indegree = [0] * n

for u, v in edges:
    graph[u].append(v)
    indegree[v] += 1

graph[u]: u에서 나가는 간선의 도착 노드 리스트
indegree[v]: v로 들어오는 간선의 수

BFS 위상정렬

python

dq = deque([i for i in range(n) if indegree[i] == 0])

진입차수가 0인 노드, 즉 앞에 와야 할 학생이 없는 학생부터 시작한다.

python

while dq:
    node = dq.popleft()
    result.append(node)
    for nxt in graph[node]:
        indegree[nxt] -= 1
        if indegree[nxt] == 0:
            dq.append(nxt)

노드를 꺼낼 때마다 연결된 노드의 진입차수를 줄이고, 0이 되면 큐에 추가한다.

사이클 감지

python

if len(result) != n:
    return []

모든 노드가 결과에 포함되지 않으면 사이클이 존재한다는 의미이다. (이 문제에서는 사이클이 없다고 보장됨)

출력

python

print(*[x + 1 for x in result])

0-indexed 결과를 다시 1-indexed로 변환하여 출력한다.

⏱ 시간복잡도

그래프 구성: O(M)
위상정렬: O(N + M)
전체: O(N + M)

N은 최대 32,000, M은 최대 100,000이므로 최대 약 132,000번의 연산으로 충분히 시간 안에 통과한다.

✨ 위상 정렬

사이클이 없는 방향 그래프(DAG)의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것을 의미
예) 선수 과목을 고려한 학습 순서 설정

위상 정렬 동작 예시 (큐)

진입 차수가 0인 모든 노드를 큐에 넣기
큐가 빌때까지 다음의 과정 반복
1. 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거
2. 새롭게 진입차수가 0이 된 노드를 큐에 넣기

위상 정렬의 특징

여러 가지 답이 존재할 수 있음
- 한 단계에서 큐에 새롭게 들어가는 원소가 2개이상인 경우가 있다면 여러가지 답이 존재
모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재
스택을 활용한 DFS를 이용해 위상정렬 수행 가능

위상 정렬 BFS 코드

from collections import deque, defaultdict 

def topological_sort_bfs(n, edges):
  """
  n: 노드수 (0~n-1)
  edges: [(u,v), ...] u->v 방향 간선 
  """
  
  graph = defaultdict(list)
  indegree = [0] * n 

  for u, v in edges:
    graph[u].append(v)
    indegree[v] += 1

  dq = deque([i for i in range(n) if indegree[i] == 0 ]_
  result = []

  while dq:
    node = dq.popleft()
    result.append(node)
    for next in graph[nodex]:
      indegree[next] -= 1:
      if indegree[next] == 0:
        dq.append(next)

  if len(result) != n: 
    return [] # 사이클 존재 
  return result

진입차수(indegree)가 0인 노드부터 큐에 넣고, 하나씩 꺼내며 연결된 노드의 진입차수를 하나씩 줄여가는 방식

위상정렬 DFS 코드

from collections import defaultdict

def topological_sort_dfs(n,edges):
  graph = defaultdict(list)
  for u,v in edges:
    graph[u].append(v)

  visited = [0] * n # 0 미방문 1 진행중 2완료
  result = [] 

  def dfs(node):
    if visited[node] == 1:
      return False
    if visited[node] == 2:
      return True 
    for next in graph[node]:
      if not dfs(next):
        return False 
    visited[node] = 2
    result.append(node)
    return True
 
for i in range(n):
  if visited[i] == 0:
    if not dfs(i):
      return []

  return result[::-1]