[백준/Python]2252: 줄 세우기

문제

https://www.acmicpc.net/problem/2252
백준 문제집 - 0x1A강 - 위상 정렬

 

알고리즘: 위상 정렬

---

풀이

 

위상 정렬 자체를 처음 접해봤던 파트다.

위상정렬(Topological Sorting): DAG(방향 사이클이 없는 방향 그래프)의 노드들을 순서화
BFS, DFS 모두 가능. 그래프는 단방향으로 저장한다.

 

전체 코드

1️⃣ DFS 방식

# 1. DFS 사용
# 진입차수(in-degree) 불필요
# 메모리: 39328KB / 시간: 156ms
from sys import stdin


input = stdin.readline

N, M = map(int, input().split())
graph = [[] for _ in range(N+1)]

for _ in range(M):
    u, v = map(int, input().split())

    graph[u].append(v)


def dfs():
    stack = []
    visited = [False] * (N+1)
    ret = []

    for i in range(1, N+1):
        if visited[i]:
            continue

        stack.append((i, False))

        while stack:
            curr, is_done = stack.pop()  # (현재 노드, 후처리 여부)

            if is_done:  # ✅ 후처리 단계 - 자식 노드를 모두 방문 후 본인 노드 처리
                ret.append(curr)
                continue

            if visited[curr]:  # 이미 방문한 노드면 무시
                continue

            visited[curr] = True  # 현재 노드 방문처리, 후처리를 위해 다시 push
            stack.append((curr, True))

            for node in graph[curr]:
                if not visited[node]:
                    stack.append((node, False))
    return ret[::-1]  # 뒤집어서 반환


print(*dfs())

재귀가 아닌 단순 반복으로 DFS를 수행하기 때문에, is_done으로 방문 시점/후처리 시점을 구분해줘야한다.
(물론 그래프가 1 - 4 - 3 - 6... 이런식으로 최소 간선으로 구성되어 있다면 필요 X)

 

실행 로직은 다음과 같다.

1. 모든 노드에 대해 방문하지 않은 노드를 찾아 DFS 시작
2. 스택에 시작 노드를 (노드, False)형태로 삽입. 여기서 False는 아직 후처리되지 않았음을 의미한다.
3. 스택이 빌 때까지 아래를 반복한다.
   • 스택에서 (현재 노드, 후처리 여부) 꺼내기
   • 만약 후처리 여부가 True라면,
     • 결과 리스트에 현재 노드를 추가 후 계속 진행
   • 만약 이미 방문한 노드라면,
     • 무시하고 계속 진행
   • 아직 방문하지 않은 노드라면,
     • 방문 처리 (visited[현재 노드] = True)
     • 후처리를 위해 (현재 노드, True) 형태로 다시 스택에 추가
     • 현재 노드의 인접 노드 중 방문하지 않은 노드를 (인접 노드, False)형태로 스택에 추가
4. 모든 노드에 대한 처리가 끝나면 결과 리스트를 뒤집어서 반환

DFS가 끝나는 순간 = 해당 정점과 그 정점에서 도달할 수 있는 모든 정점을 방문했을때
이므로, 결과 리스트에는 끝 순번부터 차례로 들어가게 된다.
따라서 마지막에 뒤집어줘야 우리가 원하는 위상 정렬 순서를 얻을 수 있음.

 

그리고 중간에 if visited[curr]조건이 없다면 순서쌍이 뒤죽박죽으로 주어졌을 경우 틀린 답이 도출된다.

# 반례
3 3
1 3
2 3
1 2
답: 1 2 3
결과: 1 3 2 3

---

2️⃣ BFS 방식

# 2. BFS 사용
# 진입차수(in-degree)로 체크
# 메모리: 40908KB / 시간: 188ms
from sys import stdin
from collections import deque


input = stdin.readline

N, M = map(int, input().split())
graph = [[] for _ in range(N+1)]
degree = [0] * (N+1)

for _ in range(M):
    u, v = map(int, input().split())

    degree[v] += 1
    graph[u].append(v)

queue = deque()
visited = [False] * (N+1)
ret = []

for i in range(1, N+1):
    if not degree[i]:
        queue.append(i)
        visited[i] = True

def bfs():
    while queue:
        curr = queue.popleft()
        ret.append(curr)

        for node in graph[curr]:
            if not visited[node]:
                degree[node] -= 1
                if degree[node] == 0:
                    queue.append(node)
                    visited[node] = True

bfs()
print(*ret)

사실 난 BFS를 사용하는 방식이 더 편하다.
로직 자체도 익숙하거니와 한눈에 알아보기 쉽다...

 

다만 BFS를 사용할때에는 노드들의 진입차수(in-degree)를 먼저 정리해줘야한다.

뭔 말이냐하면, 문제와 같이 "A가 B앞에 서야한다"처럼 어떤 한 노드가 다른 노드 앞에 위치해야한다고 했을때

그래프의 흐름은 A → B 와 같이 이루어진다.

따라서 A의 진입차수는 0, B의 진입차수는 1이 되는것이다.

하지만 문제에 따라서 A가 먼저 실행되는것같아도 B → A와 같이 정리해야 할 수도 있으므로 주의해야한다.

 

BFS방식의 실행 과정은 다음과 같다.

1. 모든 노드의 진입차수(in-degree)를 계산한다.
2. 진입차수가 0인 모든 노드를 찾아 큐에 삽입한다.
   • 이 노드들은 선행 조건이 없어 바로 시작할 수 있는 노드들임.
3. 큐가 빌 때까지 아래를 반복한다.
   • 큐에서 노드를 pop한다.
   • 결과 리스트에 꺼낸 현재 노드를 추가.
   • 현재 노드에 인접한 모든 노드에 대해, 
     • 해당 노드의 진입차수를 1 감소시킴.
     • 진입차수가 0이 되면 노드를 큐에 삽입 후 방문처리한다.
4. 모든 노드가 처리되었으면 끝. 결과 리스트에 위상 정렬의 결과가 그대로 저장되어있다.

 

문제에 따라 효율적인 방식이 달라진다.