728x90
문제풀이
위상정렬은 순서가 정해져있는 작업을 차례대로 수행해야 할 때 그 순서를 결정해주기 위해 사용하는 알고리즘 이다.
보통의 경우 어떤 조건을 주고 순서대로 나열하는 경우를 물어본다.
이 줄세우기 문제는 인적성 시험? 볼때 이런 경우일때 참,거짓을 물어보는 문제를 풀었던 기억이 난다.
알고리즘 자체는 어렵지 않은데 이 방법을 생각해내기는 어려울 것 같다.
다음의 유튜브를 참고 하였다.
https://www.youtube.com/watch?v=qzfeVeajuyc&t=709s
소스코드
|
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
|
import java.util.*;
import java.io.*;
class Main{
static int n,m;
static int[] inDegree;
static List<Integer>[] nodes;
static int[] result;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
inDegree = new int[n+1];
nodes = new ArrayList[n+1];
result = new int[n+1];
for(int i=1;i<=n;i++)
nodes[i] = new ArrayList<>();
for(int i=0;i<m;i++)
{
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
nodes[a].add(b);
inDegree[b]++;
}
topologySort();
for(int i=1;i<=n;i++)
{
System.out.print(result[i] + " ");
}
}
static void topologySort()
{
Queue<Integer> q = new LinkedList<>();
for(int i=1;i<=n;i++)
{
if(inDegree[i] == 0)
q.add(i);
}
for(int i=1;i<=n;i++)
{
if(q.isEmpty()) break;
int x = q.poll();
result[i] = x;
for(int j=0;j<nodes[x].size();j++)
{
int y = nodes[x].get(j);
inDegree[y]--;
if(inDegree[y] == 0)
q.add(y);
}
}
}
}
|
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
LIST
'Programming > Algorithm' 카테고리의 다른 글
| [Sort] BOJ 10610번, 30(JAVA) (0) | 2021.11.01 |
|---|---|
| [Sort] BOJ 1181번, 단어 정렬(JAVA) (2) | 2021.10.31 |
| [Kruskal MST] BOJ 1197번, 최소 스패닝 트리(JAVA) (0) | 2021.10.29 |
| [BFS] BOJ 2583번, 영역 구하기(JAVA) (0) | 2021.10.28 |
| [BFS] BOJ 7562번, 나이트의 이동(JAVA) (0) | 2021.10.28 |