2252번: 줄 세우기
첫째 줄에 N(1≤N≤32,000), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이다. 학생들의 번호는 1번부터 N번이다.
www.acmicpc.net
위상 정렬 기본 문제이다.
위상 정렬이 무엇인가 하면, 어떤 유향 그래프가 있을 때 선후 관계를 해치지 않도록 노드를 정렬하는 것이다.
당연하게도 이 유향 그래프에는 사이클이 있으면 안 된다. 사이클이 있으면 선후 관계라는 게 있을 수가 없기 때문이다.
위상 정렬을 하는 방법은 두 가지가 있다. 하나는 재귀를 사용하는 방법, 다른 하나는 재귀를 사용하는 방법이다.
조금 더 직관적이지만 구현이 복잡한 노 재귀 방법부터 보자.
다음과 같은 사이클이 없는 유향그래프가 있고, 정렬된 배열을 S라고 하자.
첫 번째 방법은 한 마디로 설명하면 '시작 노드를 그래프에서 빼서 순서대로 놓는 것'이다.
시작노드들이란 그 노드로 들어오는 간선이 없는 노드들을 말한다.
즉 인접 리스트 등에서 어떤 노드보다 뒤에 있다고 설명되지 않는 노드들이다.
초기 그래프와 정렬된(텅 빈) 배열 S이다.
여기서 시작노드들은 1과 5이다. 노드 1이나 5로 들어오는 간선이 없기 때문에 1과 5는 시작 노드이다.
위상 정렬을 하기 위해서는 이 시작 노드 중 하나를 선택해서, 그 노드와 그 노드로부터 출발하는 진출 간선을 모두 삭제한다. 1을 선택해보자.
1과 1의 진출 간선이 삭제되었다. 그리고 1이 정렬된 배열 S의 맨 뒤에 추가되었다.
간단하게도 이것을 계속 반복하면 된다.
삭제된 1의 진출 간선과 연결되어 있던 2는 진입 간선을 하나 잃었다. (1의 진출 간선=2의 진입 간선)
이제 진입 간선이 없는 시작 노드는 2, 5가 되었다. 다시 그 중에서 하나를 선택해 그 노드와 진출 간선을 모두 삭제한다. 이번에는 2를 선택해보자.
2를 삭제하고 2로부터 출발하는 진출 간선들을 모두 삭제했다. 그리고 2를 정렬된 배열 S의 맨 뒤에 추가했다.
이제 시작 노드는 5 하나이다.
5를 삭제하고 배열 S에 추가했고, 5로부터 출발하는 5의 진출 간선들을 모두 삭제했다.
이제 시작 노드는 4와 6이다. 이 중 4를 선택해보자.
4를 삭제하고 배열 S에 추가한 뒤, 4의 진출 간선들을 모두 삭제했다.
이제 시작 노드는 6 하나 뿐이다.
6을 삭제하고 배열 S에 추가했다. 그리고 배열 S에 추가했다.
이제 시작 노드는 3 하나 뿐이다.
3을 삭제하고 배열 S의 맨 뒤에 추가했다. 이제 남은 노드가 없으므로 배열 S가 위상 정렬이 완료된 배열이 되었다.
import sys
def solution():
for _ in range(N):
u = start_v.pop() # 시작 노드 중 하나를 꺼낸다
answer.append(u+1) # 배열의 맨 뒤에 삽입
for node in out[u]: # 노드 u와 연결된 간선들을 삭제하면 그 간선들과 연결된 노드들의 진입 간선 수가 줄어든다
in_num[node] -= 1
if in_num[node] == 0: # 진입 간선이 0이 된 간선은 시작 노드 배열에 추가
start_v.append(node)
answer = []
input = sys.stdin.readline
N, M = map(int, input().split()) # N = 학생수, M = 비교횟수
start_v = [] # 진입 간선이 0인 시작 노드
in_num = [0 for _ in range(N)] # 진입 간선의 수. in_num=0인 노드가 시작 노드가 된다
out = [[] for _ in range(N)] # 모든 노드에 대해 선후 관계를 정리한 배열
# 노드들의 선후 관계가 입력으로 들어온다. 배열의 인덱스는 0부터 시작이므로 각각 1씩 마이너스해서 배열에 담는다.
for _ in range(M):
a, b = map(int, input().split())
out[a-1].append(b-1)
in_num[b-1] += 1
for idx, num in enumerate(in_num):
if num == 0:
start_v.append(idx) # 진입간선이 0인 정점들은 먼저 줄세운다
solution()
for a in answer:
print(a, end=' ')
두 번째 방법은 재귀를 이용하는 것이다. 모습이 DFS를 닮았기 때문에 DFS 방법이라고 한다.
이번에는 아무 노드나 선택한 후, 그 노드와 연결된 노드들을 재귀로 찾아서 배열의 맨 앞에 삽입하면 된다.
import sys
from collections import deque
def solution():
for i in range(N):
if not visited[i]:
dfs(i)
def dfs(v):
visited[v] = True
for next_v in out[v]:
if not visited[next_v]:
dfs(next_v)
answer.appendleft(v+1)
answer = deque()
input = sys.stdin.readline
N, M = map(int, input().split()) # N = 학생수, M = 비교횟수
visited = [False for _ in range(N)]
out = [[] for _ in range(N)] # 인접 리스트. 진출 간선들을 정리한 리스트.
for _ in range(M):
a, b = map(int, input().split())
out[a-1].append(b-1)
solution()
for a in answer:
print(a, end=' ')
'알고리즘 > 그외중요한것들' 카테고리의 다른 글
| 완주하지 못한 선수 (Python) (0) | 2020.07.03 |
|---|---|
| 리스트 얕은 복사 후 기존 값을 다른 것으로 대체하면 (0) | 2020.04.23 |
| 2003번. 수들의 합 2 (0) | 2020.03.30 |
