2252번: 줄 세우기
첫째 줄에 N(1≤N≤32,000), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이
www.acmicpc.net
자신보다 뒤에 서야하는 학생의 번호를 list에 넣습니다.
그리고 뒤에 서야하는 학생의 번호는 conn 배열을 이용하여 자신보다 앞에 서야하는 학생이 몇명인지 유지합니다.
그 다음 conn[i]이 0인 학생들의 번호만 큐에 추가한 후에 bfs를 돌립니다.
먼저 번호 x보다 뒤에 서야하는 번호를 하나씩 확인하여 conn[y]--를 해줍니다.
conn[y]=0이 되면 자신보다 앞에 있어야할 번호를 모두 탐색을 했으므로 y를 큐에 추가합니다.
이런 방식으로 ans에 번호를 차례대로 쌓는 방식입니다.
이 문제는 줄을 못 세우는 경우가 없기 때문에 ans의 크기가 N보다 작은지 확인하는 예외처리를 하지 않았습니다.
만약 문제에서 이런 경우는 요구하면 무조건 해줘야하는 예외케이스 입니다.
|
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
62
63
64
65
66
67
68
69
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static StringBuffer sb = new StringBuffer();
static ArrayList<Integer> list[] = new ArrayList[32001];
static ArrayList<Integer> ans = new ArrayList<>();
static int conn[] = new int[32001];
static int N, M;
static void print() {
for (int i = 0; i < ans.size(); i++) {
sb.append(ans.get(i) + " ");
}
System.out.println(sb.toString());
}
static void func() {
Queue<Integer> q = new LinkedList<>();
for (int i = 1; i <= N; i++) {
if (conn[i] == 0) {
q.add(i);
}
}
while (!q.isEmpty()) {
int x = q.poll();
ans.add(x);
for (int i = 0; i < list[x].size(); i++) {
int y = list[x].get(i);
conn[y]--;
if (conn[y] == 0)
q.add(y);
}
}
}
static void input() throws Exception {
int u, v;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
for (int i = 1; i <= N; i++)
list[i] = new ArrayList<>();
while (M-- > 0) {
st = new StringTokenizer(br.readLine());
u = Integer.parseInt(st.nextToken());
v = Integer.parseInt(st.nextToken());
list[u].add(v);
conn[v]++;
}
}
public static void main(String[] args) throws Exception {
input();
func();
print();
}
}
|
cs |
'algorithm > Topological-sort' 카테고리의 다른 글
| boj 23059 리그 오브 레게노 (0) | 2021.12.15 |
|---|