Coding Test

๋ฐฑ์ค€ 14567๋ฒˆ : ์„ ์ˆ˜๊ณผ๋ชฉ (Prerequisite) ์ž๋ฐ” - ์˜ˆ์™ธ๋ฌธ ๋ฐ ์˜ค๋‹ต๋…ธํŠธ

ํ”„๋กœ๊ทธ๋ž˜๋จธ ์˜ค์›” 2023. 8. 10.

๋ฐฑ์ค€ 14567๋ฒˆ : ์„ ์ˆ˜๊ณผ๋ชฉ (Prerequisite)

 

 

https://www.acmicpc.net/problem/14567

 

14567๋ฒˆ: ์„ ์ˆ˜๊ณผ๋ชฉ (Prerequisite)

3๊ฐœ์˜ ๊ณผ๋ชฉ์ด ์žˆ๊ณ , 2๋ฒˆ ๊ณผ๋ชฉ์„ ์ด์ˆ˜ํ•˜๊ธฐ ์œ„ํ•ด์„œ๋Š” 1๋ฒˆ ๊ณผ๋ชฉ์„ ์ด์ˆ˜ํ•ด์•ผ ํ•˜๊ณ , 3๋ฒˆ ๊ณผ๋ชฉ์„ ์ด์ˆ˜ํ•˜๊ธฐ ์œ„ํ•ด์„œ๋Š” 2๋ฒˆ ๊ณผ๋ชฉ์„ ์ด์ˆ˜ํ•ด์•ผ ํ•œ๋‹ค.

www.acmicpc.net

 

๋ฌธ์ œ

์˜ฌํ•ด Z๋Œ€ํ•™ ์ปดํ“จํ„ฐ๊ณตํ•™๋ถ€์— ์ƒˆ๋กœ ์ž…ํ•™ํ•œ ๋ฏผ์šฑ์ด๋Š” ํ•™๋ถ€์— ๊ฐœ์„ค๋œ ๋ชจ๋“  ์ „๊ณต๊ณผ๋ชฉ์„ ๋“ฃ๊ณ  ์กธ์—…ํ•˜๋ ค๋Š” ์›๋Œ€ํ•œ ๋ชฉํ‘œ๋ฅผ ์„ธ์› ๋‹ค. ์–ด๋–ค ๊ณผ๋ชฉ๋“ค์€ ์„ ์ˆ˜๊ณผ๋ชฉ์ด ์žˆ์–ด ํ•ด๋‹น๋˜๋Š” ๋ชจ๋“  ๊ณผ๋ชฉ์„ ๋จผ์ € ์ด์ˆ˜ํ•ด์•ผ๋งŒ ํ•ด๋‹น ๊ณผ๋ชฉ์„ ์ด์ˆ˜ํ•  ์ˆ˜ ์žˆ๊ฒŒ ๋˜์–ด ์žˆ๋‹ค. ๊ณตํ•™์ธ์ฆ์„ ํฌ๊ธฐํ•  ์ˆ˜ ์—†๋Š” ๋ถˆ์Œํ•œ ๋ฏผ์šฑ์ด๋Š” ์„ ์ˆ˜๊ณผ๋ชฉ ์กฐ๊ฑด์„ ๋ฐ˜๋“œ์‹œ ์ง€์ผœ์•ผ๋งŒ ํ•œ๋‹ค. ๋ฏผ์šฑ์ด๋Š” ์„ ์ˆ˜๊ณผ๋ชฉ ์กฐ๊ฑด์„ ์ง€ํ‚ฌ ๊ฒฝ์šฐ ๊ฐ๊ฐ์˜ ์ „๊ณต๊ณผ๋ชฉ์„ ์–ธ์ œ ์ด์ˆ˜ํ•  ์ˆ˜ ์žˆ๋Š”์ง€ ๊ถ๊ธˆํ•ด์กŒ๋‹ค. ๊ณ„์‚ฐ์„ ํŽธ๋ฆฌํ•˜๊ฒŒ ํ•˜๊ธฐ ์œ„ํ•ด ์•„๋ž˜์™€ ๊ฐ™์ด ์กฐ๊ฑด์„ ๊ฐ„์†Œํ™”ํ•˜์—ฌ ๊ณ„์‚ฐํ•˜๊ธฐ๋กœ ํ•˜์˜€๋‹ค.

  1. ํ•œ ํ•™๊ธฐ์— ๋“ค์„ ์ˆ˜ ์žˆ๋Š” ๊ณผ๋ชฉ ์ˆ˜์—๋Š” ์ œํ•œ์ด ์—†๋‹ค.
  2. ๋ชจ๋“  ๊ณผ๋ชฉ์€ ๋งค ํ•™๊ธฐ ํ•ญ์ƒ ๊ฐœ์„ค๋œ๋‹ค.

๋ชจ๋“  ๊ณผ๋ชฉ์— ๋Œ€ํ•ด ๊ฐ ๊ณผ๋ชฉ์„ ์ด์ˆ˜ํ•˜๋ ค๋ฉด ์ตœ์†Œ ๋ช‡ ํ•™๊ธฐ๊ฐ€ ๊ฑธ๋ฆฌ๋Š”์ง€ ๊ณ„์‚ฐํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์—ฌ๋ผ.

์ž…๋ ฅ

์ฒซ ๋ฒˆ์งธ ์ค„์— ๊ณผ๋ชฉ์˜ ์ˆ˜ 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 ํ–‰์ด ์ง„ํ–‰์ฐจ์ˆ˜ ๋ฐฐ์—ด์ด๋‹ค.

๋Œ“๊ธ€