[Algorithm]Baekjoon 14567번 : 선수과목 (Prerequisite)

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

14567번: 선수과목 (Prerequisite)

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
#include <numeric>
 
using namespace std;
 
 
int n, m;
vector<vector<int>> graph(1001);
int maxDepth[1001] = { 0 };
int inDegrees[1001] = { 0 };
 
 
void DFS(int node)
{
    int curDepth = maxDepth[node];
 
    for (int i = 0; i < graph[node].size(); ++i)
    {
        int nextNode = graph[node][i];
 
        if (curDepth + 1 <= maxDepth[nextNode]) continue;
 
        maxDepth[nextNode] = curDepth+1;
        DFS(nextNode);
    }
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n >> m;
 
    for (int i = 0; i < m; ++i)
    {
        int a, b;
        cin >> a >> b;
 
        graph[a].push_back(b);
        ++inDegrees[b];
    }
 
    for (int i = 1; i <= n; ++i)
    {
        if (inDegrees[i] == 0)
        {
            maxDepth[i] = 1;
            DFS(i);
        }
    }
 
    for (int i = 1; i <= n; ++i)
    {
        printf("%d ", maxDepth[i]);
    }
}

 

선수과목..이란 단어가 나오면 거진 위상정렬느낌의 문제인 경우가 많다.

그래프의 시작지점은 inDegree값이 0인것부터 시작이다. 즉, 선수과목이 아예 없는 과목부터 시작해야한다.

 

선수과목이 없는과목은 여러개가 될 수 있는데, 그러다보니 각각의 시작지점에서 특정노드에 갔을 때 깊이가 다르다.

문제에서의 테스트케이스2번의 경우 아래와 같다.

 

6 4
1 2
1 3
2 5
4 5

 

5번과목같은 경우 1번에서 시작하면 2를 거쳐서야 도착한다.즉, 깊이가 3이다.

근데 4부터 시작하면 바로 도착한다. 즉, 깊이가 2이다.

학기마다 하나의 과목만 들을 수 있기 때문에 최종적으로 5번과목은 반드시 3학기에 들을 수 있기때문에 3을 출력해줘야 한다.

이 점을 반영해, inDegree값이 0인것부터 시작해서 깊이탐색을 할 건데, 만약 자식의 깊이값이 현재깊이값 +1보다 작거나 같으면 더이상 탐색할 이유가 없기 때문에 하지 않는다.

그러나 현재깊이값 +1보다 크다면, 반드시 업데이트 해줘야함과 동시에 또 그 밑의 자식들에 대해서 값을 업데이트해줘야하기때문에 깊이탐색을 해줘야 한다.

.

.

.

은 사실, 자식들에 대해서 값을 재업데이트해주는 과정은 불필요하다.

이건 위상정렬처럼 풀어도 되고, 그냥 최대깊이자식값을 구하면서 dp값업데이트 해주는식으로 풀어도 된다.

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
#include <numeric>
 
using namespace std;
 
 
int n, m;
vector<vector<int>> graph(1001);
int maxDepth[1001] = { 0 };
int inDegrees[1001] = { 0 };
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n >> m;
 
    for (int i = 0; i < m; ++i)
    {
        int a, b;
        cin >> a >> b;
 
        graph[a].push_back(b);
        ++inDegrees[b];
    }
 
    queue<pair<int, int>> q;
    
    for (int i = 1; i <= n; ++i)
    {
        if (inDegrees[i] == 0)
        {
            q.push({ i,1 });
        }
    }
 
    while (!q.empty())
    {
        int curNode = q.front().first;
        int curDepth = q.front().second;
        q.pop();
 
        maxDepth[curNode] = curDepth;
 
        for (int nextNode : graph[curNode])
        {
            --inDegrees[nextNode];
            if (inDegrees[nextNode] == 0)
            {
                q.push({ nextNode, curDepth + 1 });
            }
        }
    }
 
    for (int i = 1; i <= n; ++i)
    {
        printf("%d ", maxDepth[i]);
    }
}

 

 

위상정렬의 기본예제문제를 풀어봤다면 매우 익숙한 코드일텐데, 마찬가지로 inDegree값이 0인 노드를 큐에 넣어서 차례대로 뽑아준다.

뽑을때마다 maxDepth에 값을 업데이트해주고 자식들에 대해서 계속 뻗어갈텐데, 이 때 큐에 새로 넣기위한 조건으로 inDegrees[nextNode]값이 0일때 넣어줘야 한다.

이렇게하면 맨 처음의 깊이탐색처럼 다시 자식들에 대해서 재업데이트를 해줄필요 없이, 그냥 노드개수만큼의 탐색으로 끝낼 수 있다.

 

왜 그렇게 되냐면, inDegrees[nextNode] == 0일 때 큐에 넣어준다는 것은, nextNode의 마지막에 연결된 선행과목(즉 curNode) 의 depth값 + 1이 nextNode의 최종 depth값이 된다는 보장이 되기 때문이다.

 

다시 테스트케이스를 보자.

 

6 4
1 2
1 3
2 5
4 5

 

여기서 5번과 그 주변을 살펴보면, 1->2->5  랑 4->5  가 있다.

즉, 5의 inDegree값은 2인데 1번부터 시작하면 한단계를 거쳐야하고 4번부터 시작하면 바로 접근이 가능하다.

위 코드대로의 로직상이면, 반드시 단계가 거치는게 많을경우 목표노드에 제일 마지막으로 접근하게 된다.

 

그리고 이게 문제에서 원하는 접근이다. 특정노드(과목)에 대해서 어디서 시작하든 최대깊이를 원하기 때문에, 단계가 제일 많은 경우에 접근하는 순간을 확인해야 한다. 그 순간이 바로 inDegree[nextNode]값이 0이되는 순간이기 때문에 코드를 저런식으로 작성해야 한다. 확실하게 현재 노드의 깊이값이 최대깊이값일 때 큐에 자식들을 넣었기 때문에, 나중에 재업데이트같은 불필요한 중복과정이 필요없다.

 

 

그리고 사실, 긴 설명이 필요없는 dp + 깊이탐색 코드..

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
#include <numeric>
 
using namespace std;
 
 
int n, m;
vector<vector<int>> graph(1001);
int answers[1001] = { 0 };
int inDegrees[1001] = { 0 };
 
int DFS(int node)
{
    if (answers[node] > 0) return answers[node];
 
    int maxDepth = 0;
 
    for (int nextNode : graph[node])
    {
        maxDepth = max(maxDepth, DFS(nextNode));
    }
 
    return answers[node] = maxDepth + 1;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n >> m;
 
    for (int i = 0; i < m; ++i)
    {
        int a, b;
        cin >> a >> b;
 
        graph[b].push_back(a);
        ++inDegrees[a];
    }
 
    queue<pair<int, int>> q;
    
    for (int i = 1; i <= n; ++i)
    {
        if (inDegrees[i] == 0)
        {
            DFS(i);
        }
    }
 
    for (int i = 1; i <= n; ++i)
    {
        printf("%d ", answers[i]);
    }
}

 

여기서 inDegree라 되어있는건, 위코드들의 inDegree의 반대개념이다.

그래프입력을 a->b가 아니라 b->a로 입력받았기 때문에, 위 코드들의 관점에서 보자면 맨 끝노드가 inDegree값이 0이 되는 것이다.

즉, 맨 끝노드부터 시작하면서 자신의 하위노드의 최대깊이값을 구해서 업데이트해주는 코드이다.

한번이라도 업데이트했다면 해당값이 최대깊이값을 보장하기 때문에 이미 dp테이블에 업데이트 되어있는 노드면 해당탐색에서 바로 dp테이블값을 리턴시켜주면 중복탐색을 안할 수 있다.