๋ฐฑ์ค 14567๋ฒ : ์ ์๊ณผ๋ชฉ (Prerequisite)
https://www.acmicpc.net/problem/14567
๋ฌธ์
์ฌํด Z๋ํ ์ปดํจํฐ๊ณตํ๋ถ์ ์๋ก ์ ํํ ๋ฏผ์ฑ์ด๋ ํ๋ถ์ ๊ฐ์ค๋ ๋ชจ๋ ์ ๊ณต๊ณผ๋ชฉ์ ๋ฃ๊ณ ์กธ์ ํ๋ ค๋ ์๋ํ ๋ชฉํ๋ฅผ ์ธ์ ๋ค. ์ด๋ค ๊ณผ๋ชฉ๋ค์ ์ ์๊ณผ๋ชฉ์ด ์์ด ํด๋น๋๋ ๋ชจ๋ ๊ณผ๋ชฉ์ ๋จผ์ ์ด์ํด์ผ๋ง ํด๋น ๊ณผ๋ชฉ์ ์ด์ํ ์ ์๊ฒ ๋์ด ์๋ค. ๊ณตํ์ธ์ฆ์ ํฌ๊ธฐํ ์ ์๋ ๋ถ์ํ ๋ฏผ์ฑ์ด๋ ์ ์๊ณผ๋ชฉ ์กฐ๊ฑด์ ๋ฐ๋์ ์ง์ผ์ผ๋ง ํ๋ค. ๋ฏผ์ฑ์ด๋ ์ ์๊ณผ๋ชฉ ์กฐ๊ฑด์ ์งํฌ ๊ฒฝ์ฐ ๊ฐ๊ฐ์ ์ ๊ณต๊ณผ๋ชฉ์ ์ธ์ ์ด์ํ ์ ์๋์ง ๊ถ๊ธํด์ก๋ค. ๊ณ์ฐ์ ํธ๋ฆฌํ๊ฒ ํ๊ธฐ ์ํด ์๋์ ๊ฐ์ด ์กฐ๊ฑด์ ๊ฐ์ํํ์ฌ ๊ณ์ฐํ๊ธฐ๋ก ํ์๋ค.
- ํ ํ๊ธฐ์ ๋ค์ ์ ์๋ ๊ณผ๋ชฉ ์์๋ ์ ํ์ด ์๋ค.
- ๋ชจ๋ ๊ณผ๋ชฉ์ ๋งค ํ๊ธฐ ํญ์ ๊ฐ์ค๋๋ค.
๋ชจ๋ ๊ณผ๋ชฉ์ ๋ํด ๊ฐ ๊ณผ๋ชฉ์ ์ด์ํ๋ ค๋ฉด ์ต์ ๋ช ํ๊ธฐ๊ฐ ๊ฑธ๋ฆฌ๋์ง ๊ณ์ฐํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์ฌ๋ผ.
์ ๋ ฅ
์ฒซ ๋ฒ์งธ ์ค์ ๊ณผ๋ชฉ์ ์ N(1 ≤ N ≤ 1000)๊ณผ ์ ์ ์กฐ๊ฑด์ ์ M(0 ≤ M ≤ 500000)์ด ์ฃผ์ด์ง๋ค. ์ ์๊ณผ๋ชฉ ์กฐ๊ฑด์ M๊ฐ์ ์ค์ ๊ฑธ์ณ ํ ์ค์ ์ ์ A B ํํ๋ก ์ฃผ์ด์ง๋ค. A๋ฒ ๊ณผ๋ชฉ์ด B๋ฒ ๊ณผ๋ชฉ์ ์ ์๊ณผ๋ชฉ์ด๋ค. A < B์ธ ์ ๋ ฅ๋ง ์ฃผ์ด์ง๋ค. (1 ≤ A < B ≤ N)
์ถ๋ ฅ
1๋ฒ ๊ณผ๋ชฉ๋ถํฐ N๋ฒ ๊ณผ๋ชฉ๊น์ง ์ฐจ๋ก๋๋ก ์ต์ ๋ช ํ๊ธฐ์ ์ด์ํ ์ ์๋์ง๋ฅผ ํ ์ค์ ๊ณต๋ฐฑ์ผ๋ก ๊ตฌ๋ถํ์ฌ ์ถ๋ ฅํ๋ค.
์์ ์ ๋ ฅ 1
3 2
2 3
1 2
์์ ์ถ๋ ฅ 1
1 2 3
์์ ์ ๋ ฅ 2
6 4
1 2
1 3
2 5
4 5
์์ ์ถ๋ ฅ 2
1 2 2 1 3 1
ํ๋ฆฐ ํ์ด
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.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Prerequisite02 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int vertexNum = Integer.parseInt(st.nextToken());
int indegreeNum = Integer.parseInt(st.nextToken());
int[][] graph = new int[vertexNum + 1][vertexNum + 1];
for (int i = 0; i < indegreeNum; i++) {
StringTokenizer stPrerequisite = new StringTokenizer(br.readLine(), " ");
int prerequisite = Integer.parseInt(stPrerequisite.nextToken());
int subSubject = Integer.parseInt(stPrerequisite.nextToken());
graph[prerequisite][subSubject] = 1;
}
List<Integer> rootVertexNumList = new ArrayList<>();
Map<Integer, Integer> result = new HashMap<>();
for (int i = 1; i <= vertexNum; i++) {
int cnt = 0;
for (int j = 1; j <= vertexNum; j++) {
if (graph[j][i] == 0) {
cnt++;
}
if (cnt == vertexNum) {
rootVertexNumList.add(i);
result.put(i, 1);
}
}
}
Set<Integer> visited = new HashSet<>();
for (int rootVertexNum : rootVertexNumList) {
Queue<Integer> queue = new LinkedList<>();
queue.add(rootVertexNum);
while (!queue.isEmpty()) {
int vertex = queue.poll();
if (!visited.contains(vertex)) {
for (int i = 1; i <= vertexNum; i++) {
if (graph[vertex][i] == 1) {
queue.add(i);
if (result.containsKey(i)) {
if (result.get(i) < result.get(vertex) + 1) {
result.replace(i, result.get(vertex) + 1);
}
} else {
result.put(i, result.get(vertex) + 1);
}
}
}
}
visited.add(vertex);
}
}
StringBuilder sb = new StringBuilder();
for (int i = 1; i < vertexNum; i++) {
sb.append(result.get(i) + " ");
}
sb.append(result.get(vertexNum));
System.out.println(sb);
}
}
|
cs |
์์ ๋ฌธ์ ๋ง๊ฒ ์ ๋์ค์ง๋ง ๊ณ์ ํ๋ ธ๋ค๊ณ ๋ฌ๋ค.
์์ธ๋ฌธ์ ์๋ฌด๋ฆฌ ์๊ฐํด๋ด๋ ์ ๋ ์ฌ๋ผ์ ์ง์ ์์ธ๋ฌธ์ ๋ง๋ค์ด ๋ณด์๋ค.
3 0
โถ 1 1 1
6 3
1 2
3 4
5 6
โถ 1 2 1 2 1 2
9 6
1 7
3 7
4 7
7 8
8 9
2 6
โถ 1 1 1 1 1 2 2 3 4
9 8
1 7
7 8
8 9
3 7
4 7
4 8
2 4
6 8
โถ 1 1 1 2 1 1 3 3 4
9 9
1 3
3 4
6 7
2 5
8 9
5 8
5 7
4 5
7 8
โถ 1 1 2 3 4 1 5 6 7
12 14
9 10
9 11
9 12
1 12
8 9
2 3
3 4
5 6
4 6
6 7
7 8
6 12
6 9
7 10
โถ 1 1 2 3 1 4 5 6 7 6 6 6
โถ 1 1 2 3 1 4 5 6 7 8 8 8
๋ง์ง๋ง ์๋ฌธ์์ ํ๋ฆฐ ์ ์ ์ฐพ์๋๋ค!!!!
10, 11, 12 ๊ฐ์ด ํ๋ฆฌ๊ฒ ๋์จ๋ค.
8์ด ๋์์ผํ๋๋ฐ 6์ด ๋์๋ค.
์ด์ ๋ ์ด๋ฌํ๋ค.
๋นจ๊ฐ ์ ๋ผ์ธ์ผ๋ก ๊ฐ์ผ์ง ์ ๋ต์ด ๋์ถ ๋๋๋ฐ, ํ์์ ํ๋์ ๋ผ์ธ์ ๋ฐ๋ผ 6๋ฒ์ ๋ค๋ฆฌ๊ณ 9๋ฒ์ ๊ฐ๊ณ 10, 11, 12์ ๋ค๋ฆฌ๊ฒ ๋๋ค. ์ด ๋ ๊ฐ์ด 6์ผ๋ก ์ ์ฅ์ด ๋๊ณ , ํ์์ 7์ ๋ฐ๋ผ 8๋ฒ๋ ๊ฐ๊ณ 9๋ฒ๋ ๊ฐ๊ณ ์ด์ 12๋ฒ์ ๊ฐ ์ฐจ๋ก์ง๋ง
๋ก์ง์ 45ํ
if (!visited.contains(vertex)) ๋๋ฌธ์ 12๋ฒ์ ์๊น 6๋ฒ์์ ๋ฐ๋ก ๋ค๋ ธ๊ธฐ ๋๋ฌธ์ ๋นจ๊ฐ ๋ผ์ธ์ 9๋ฒ์์ ๋๋๋ฒ๋ฆฐ๋ค.
๋ฌธ์ ๋ ์ ์ ํ์ต์ด ํ์ํ๊ธฐ ๋๋ฌธ์ 12๋ฒ ๊ณผ๋ชฉ์ ๋ค์ผ๋ ค๋ฉด 9๋ฒ ๊ณผ๋ชฉ 1๋ฒ ๊ณผ๋ชฉ์ ๋ชจ๋ ๋ค์ด์ผํ๋ค.
9๋ฒ ๊ณผ๋ชฉ ๊น์ง ์ต๋ ์ ์ํ์ต ํ๊ธฐ ํ์ ์๋ 6์์ ๋ฐ๋ก 9๋ฅผ ๊ฐ๋ 5๊ฐ ์๋ 6์์ 7 ,8 ๊ทธ๋ฆฌ๊ณ 9๋ฅผ ๊ฐ๋ 7์ด๋ค.
๋ฐ๋ผ์ 10, 11, 12๋ 9์ ์ต๋๊ฐ์์ +1ํ ๊ฒ ๋งํผ ํ์ํ๊ฒ ๋๋ค.
ํด๊ฒฐ ๋ฐฉ๋ฒ์ผ๋ก๋
์ฒซ๋ฒ ์งธ, ๋ฐฉ๋ฌธํ๋ ๊ณณ์ ๋๋ฝ์ํค์ง๋ง๊ณ ์ต๋๊ฐ์ ์ป๊ธฐ ์ํด ๋ฐฉ๋ฌธํ๋ ๊ณณ ๋ง์ ๋ ๋ฐฉ๋ฌธํ์ฌ ๋ชจ๋ ๊ฒฝ์ฐ์ ์๋ฅผ ๋ค ์กฐ์ฌํ๋ฉด ๋ ๊ฑฐ ๊ฐ์ 45ํ 59ํ 60ํ์ ์ฃผ์ ์ฒ๋ฆฌ ํด์คฌ๋ค.
๊ฒฐ๊ณผ๋ ์์๋๋ก ์ ๋ต์ผ๋ก ๋์๋ค.
โถ 1 1 2 3 1 4 5 6 7 8 8 8
ํ์ง๋ง ๋ชจ๋ ๊ฒฝ์ฐ์ ์์์ ๋ฐฉ๋ฌธํ๋ ๊ณณ์ ๋ ๋ค์ ๋ค ๋ค๋ฆฌ๋ ๋ฐฉ์์ผ๋ก ์ ๋ต์ ๋ฐฑ์ค์ ์ ์ถ ํ์ ๋ ์๊ฐ ์ด๊ณผ๊ฐ ๋ด๋ค.
๋๋ฒ์งธ๋ก ๊น์ด ์ฐ์ ํ์์ ์จ์ผํ๋ ์๊ฐํด์
dfs๋ฅผ ์จ์ ํ๋ฅผ ์คํ์ผ๋ก ๋ฐ๊ฟ ์คฌ์ง๋ง ๋๊ฐ์ ์ค๋ฅ๊ฐ ๋์๋ค.
ํด๊ฒฐ๋ฒ
์งํ ์ฐจ์๋ฅผ ์ฒดํฌํด์ฃผ๋ ๋ฐฐ์ด์ ํ๋ ๋ง๋ค์๋ค. 12๋ฒ ๋ ธ๋๋ฅผ ๊ฐ๋ ์งํ ์ฐจ์๋ ์ด 3๊ฐ๊ฐ ์๋๋ฐ 1,2์์ ๋๋๋ฒ๋ฆฌ๋ ์ ํํ ๋ต์ ๋์ถ ํ์ง ๋ชปํ๋ ๊ฒ์ด๋ค. ๋ฐ๋ผ์ ํ๋ฒ ๋ฃจํฌ๋ฅผ ํ์ผ๋ฉด ์งํ์ฐจ์๋ฅผ ๋นผ์ฃผ์ด ์งํ์ฐจ์๊ฐ 0์ผ ๋ ๊ฐ์ ๋ฃ์ด์ฃผ์๋ค.
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.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Prerequisite03 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int vertexNum = Integer.parseInt(st.nextToken());
int indegreeNum = Integer.parseInt(st.nextToken());
int[] in = new int[vertexNum + 1];
int[] result = new int[vertexNum + 1];
int[][] graph = new int[vertexNum + 1][vertexNum + 1];
for (int i = 0; i < indegreeNum; i++) {
StringTokenizer stPrerequisite = new StringTokenizer(br.readLine(), " ");
int prerequisite = Integer.parseInt(stPrerequisite.nextToken());
int subSubject = Integer.parseInt(stPrerequisite.nextToken());
graph[prerequisite][subSubject] = 1;
in[subSubject]++;
}
Queue<Integer> queue = new LinkedList<>();
for (int i = 1; i <= vertexNum; i++) {
int cnt = 0;
for (int j = 1; j <= vertexNum; j++) {
if (graph[j][i] == 0) {
cnt++;
}
if (cnt == vertexNum) {
queue.add(i);
}
}
}
int pre = 1;
while (!queue.isEmpty()) {
int queueSize = queue.size();
for (int x = 0; x < queueSize; x++) {
int nowVertex = queue.poll();
result[nowVertex] = pre;
for (int y = nowVertex + 1; y <= vertexNum; y++) {
if (graph[nowVertex][y] == 1) {
in[y]--;
if (in[y] == 0)
queue.add(y);
}
}
}
pre++;
}
StringBuilder sb = new StringBuilder();
for (int i = 1; i < vertexNum; i++) {
sb.append(result[i] + " ");
}
sb.append(result[vertexNum]);
System.out.println(sb);
}
}
|
cs |
12 ํ์ด ์งํ์ฐจ์ ๋ฐฐ์ด์ด๋ค.
๋๊ธ