[BOJ] 9470. Strahler 순서 + TC

* 위상정렬을 이용

* 큐에서 방문하는 노드로 들어오는 가진 강의 순서가 가장 큰 값을 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이 나온다. 

 

 

#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가 존재한다.)

 

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