문제:
N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다.
일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램을 작성하시오.
입력:
첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이다.
학생들의 번호는 1번부터 N번이다.
출력:
첫째 줄에 학생들을 키 순서대로 줄을 세운 결과를 출력한다. 답이 여러 가지인 경우에는 아무거나 출력한다.
풀이방법:
사이클이 존재하지 않고, 방향이 존재하는 그래프 상에서의 정렬을 해야 하는 문제이기 때문에 위상정렬을 사용해서 이 문제를 푼다.
위상정렬의 기본 알고리즘 진행은 다음과 같다.
1. 각 입력으로 들어온 값들을 그래프 형태로 저장한다. 이와 동시에 in_degree라는 간선이 연결된 갯수를 저장하는 배열도 같이 초기화 시킨다.
2. 모든 입력을 마친 뒤, in_degree가 0인 것부터 queue(deque)에 입력해 준다.
3. queue에서 값을 하나씩 빼면서 나온 노드들이 정렬된 것이며, 해당 노드와 연결되어 있는 선을 하나씩 제거한다.
3-1. 이 때, in_degree 값이 0이 된다면 queue에 넣는다.
4. 위 과정을 queue가 비어 있을 때까지 한다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
import sys
from collections import deque
input = sys.stdin.readline
N, M = map(int,input().split())
in_degree=[0]*(N+1)
graph = [[] for _ in range(N+1)]
queue = deque()
for _ in range(M):
a,b = map(int, input().split())
graph[a].append(b)
in_degree[b]+=1
for i in range(1, N+1):
if in_degree[i]==0:
queue.append(i)
answer = []
while queue:
now = queue.popleft()
for i in graph[now]:
in_degree[i] -=1
if in_degree[i] == 0:
queue.append(i)
answer.append(now)
print(*answer)
|
cs |
문제링크:
https://www.acmicpc.net/problem/2252
2252번: 줄 세우기
첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의
www.acmicpc.net
'Algorithm > Python' 카테고리의 다른 글
| [BOJ]1052. 물병 (0) | 2022.03.24 |
|---|---|
| [BOJ]1004. 어린 왕자 (0) | 2022.03.22 |
| [BOJ]1063. 킹 (0) | 2022.03.15 |
| [BOJ]2195. 문자열 복사 (0) | 2022.03.10 |
| [BOJ]2212. 센서 (0) | 2022.03.08 |