본문 바로가기
BOJ/C++

[BOJ] 9470. Strahler 순서 + TC

IamToday 2020. 4. 1. 15:05

* 위상정렬을 이용

* 큐에서 방문하는 노드로 들어오는 가진 강의 순서가 가장 큰 값을 maxCost[] 에 저장한다. (이 값은 항상 최대값만 저장)

* cost[]에는 가장 큰 값을 maxx라고 가정한다면 maxx가 1번 들어오면 maxx값을 그대로 저장하고 

2번이상 들어오면 maxx+1 을 저장한다. 

 

* maxCost와 cost를 따로 두어야 한다. 같은 배열에 저장한다면 maxCost[] 의 값이 변경되면서 정답이 달라지기 때문이다. 

간단하게 예를 든다면 

3 4
2 4
1 4

 

이렇게 간선이 주어져있다고 가정하자.

 

1,2,3 번 노드는 강/호수 또는 바다와 인접한 노드이므로 1의 값을 가진다. 

4번이 Strahler순서가 되는 값을 가질 텐데, indegree[4] = 3이다. 

 

처음 1의 인접리스트를 통해 4에 접근할 것이다. 

indegree[4] = 2

cost[4] = 1 (cost[1])

maxCost[4] =1 (cost[1])

 

2의 인접리스트를 통해 4에 접근 

indegree[4] = 1

maxCost[4] == cost[2] (1) 이므로 cost[4] = 2 가 될것이다. 

"가장 큰 값을 maxx라고 가정한다면 maxx가 1번 들어오면 maxx값을 그대로 저장하고 

2번이상 들어오면 maxx+1 을 저장한다"

 

마지막으로 3의 인접리스트를 통해서 4에 접근

indegree[4] = 0

maxCost[4] = 1

cost[4] = 2

 

=> maxCost[4] 가 cost[3]과 같은 값(1)을 가진다. cost[4] = maxCost[4] + 1  

 

정답은 2가 된다. 

 

만약, maxCost 없이 현재 기준이 되는 노드가 가진 값들만 비교한다면 답은 3이 나온다. 

 

 

?
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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
 
using namespace std;
 
vector<int> edge[1001];
int indegree[1001];
bool visited[1001];
typedef pair<int, int> pp;
 
int cost[1001];
int maxCost[1001];
 
int main()
{
 
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    int t;
    cin >> t;
 
    int k, p, m;
 
    while (t--)
    {
        cin >> k >> m >> p;
 
        //초기화
        for (int i = 0; i < 1001; i++)
        {
            edge[i].clear();
            visited[i] = false;
            indegree[i] = 0;
            cost[i] = 0;
            maxCost[i] = 0;
        }
 
        for (int i = 0; i < p; i++)
        {
            //간선의 정보
            int a, b;
            cin >> a >> b;
            edge[a].push_back(b);
            indegree[b]++;
        }
 
        queue<int> q;
 
        for (int i = 1; i <= m; i++)
        {
            if (!indegree[i])
            {
                q.push(i);
                visited[i] = true;
                cost[i] = 1;
                maxCost[i] = 1;
            }
        }
 
        while (!q.empty())
        {
            int now = q.front();
            q.pop();
 
            for (int next : edge[now])
            {
                //연결된 간선을 탐색
                if (!visited[next])
                {
                    indegree[next]--;
                    if (!indegree[next])
                    {
                        visited[next] = true;
 
                        q.push(next);
                    }
 
                    if (cost[next] == 0)
                    {
                        //처음 접근한 노드라면
                        cost[next] = cost[now];
                        maxCost[next] = cost[now];
                    }
                    else {
                        if (maxCost[next] < cost[now]) {
                            cost[next] = cost[now];
                            maxCost[next] = cost[now];
                        }
                        else if (maxCost[next] == cost[now]){
                            cost[next] = maxCost[next] + 1;
                        }
                    }
                }
            }
        }
        int maxx = 1;
        for (int i = 1; i <= m; i++)
        {
            maxx = maxx > cost[i] ? maxx : cost[i];
        }
        cout <<k << " " << maxx << '\n';
    }
    return 0;
}

 

+ TC (대회문제이기 때문에 공개된 TC가 존재한다.)

더보기

 

?
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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
7
1 7 8
1 3
2 3
6 4
3 4
3 5
6 7
5 7
4 7
2 20 19
1 3
2 3
3 7
4 6
5 6
6 7
8 9
7 9
9 10
11 13
12 13
13 14
15 17
16 17
17 14
14 10
10 19
18 19
19 20
3 10 9
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
4 10 9
2 3
4 5
8 9
9 10
1 2
6 7
5 6
7 8
3 4
5 13 16
1 12
12 9
9 11
11 13
2 4
4 8
8 12
8 7
9 10
10 11
7 10
4 5
5 6
3 6
6 11
5 7
6 2 1
1 2
7 5 4
4 3
3 2
2 1
1 5
     
ans
1 3
2 4
3 1
4 1
5 3
6 1
7 1

'BOJ > C++' 카테고리의 다른 글

[BOJ] 14391. 종이조각  (0) 2020.04.16
[BOJ] 1600. 말이 되고픈 원숭이  (0) 2020.04.07
[BOJ] 1280. 나무심기  (0) 2020.03.30
[BOJ] 2636. 치즈  (0) 2020.03.29
[BOJ] 18808. 스티커 붙이기  (0) 2020.03.25

'BOJ/C++' Related Articles

티스토리툴바