[c++] 백준 1766 - 문제집(DFS, brute force, priorty queue)

0. [c++] 백준  -

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

1. 풀이

1) 이렇게 푸는게 아닌 것 같기는 한데, 따로 찾아보지 않고 풀어내고 싶어서 우선 구현해보았다.

사실 이 구현은 DFS보다는 brute force에 더 가까워 보인다.

어떤식으로 구현하였나면, indegree라는 내 앞에 출력해야 하는 것이 있는지 없는지 확인하는 배열을 하나 만들어 주었고, indegree가 0이면서, 아직 출력이 되지 않은 경우 출력을 하고, 그다음 출력 할 숫자를 찾는 형식으로 구현을 하였다.

이때 출력을 하면서 자신과 관련되어있던 숫자들의 indegree를 1씩 감소시켜주었다.

처음, 구현하면서는 indegree가 감소가 된 경우 바로 깊이 탐색을 시행하였는데, 그런 경우 here에서 there사이에 존재하는 숫자 중 출력이 가능했던 더 작은 수가 출력이 되지 않는 경우가 발생했었다.

그래서 작은 수만 탐색하는 구현으로 바꾸었었는데, 이 또한 틀린 답이었었다.

결국 처음부터 탐색을 시행하는 것으로 바꾸어서 문제 해답을 이끌어 내었다.

질문을 찾아보니 우선시행큐라는 것을 활용해서 문제를 푸는 것 같던데, 이것도 한번 사용해보아야겠다.

2) priorty queue라는 것을 활용하여 문제를 해결해보았다.

이 문제에서 핵심 부분은 

1. indegree(진입차수)가 0인 경우 출력을 한다.

2. 이때, 더 작은 수를 먼저 출력해주어야 한다.

라는 것이였다.

그럼 이를 만족시키기 위해서는 어떻게 해주어야할까?

내가 위에서 구현한 것을 보면 indegree가 0인 것 중에서 가장 작은 수를 출력하기 위해서 N 범위 전체를 for문으로 돌려서 

(가장 작은 수) && (아직 출력을 안한 수) && (indegree == 0) 를 만족시키는 수를 매번 찾아내는 것을 확인 할 수 있는데,

여기서는 이러한 구현을 해주는 priorty queue라는 것을 활용하는 것이다.

priorty queue는 이진 트리의 활용의 일부분으로, heap이라는 특수한 이진 트리로 가장 작은 수가 트리의 root가 되고, 문자를 삽입, 삭제를 하는등의 구현이 O(logN)에 이루어지는 함수이다.

이를 활용하여 시간을 단축시키기에 성공하였고, 더 직관적인? 구현에 성공하였다.

priorty queue라는 것을 처음 활용해 보았는데, 이와 관련된 문제를 더 풀어보아야 몸에 습득될 것 같다.

2. 소스코드

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

#include<vector> #include<iostream> #include<algorithm>   using namespace std;   int N, M; vector<int> adj[32001]; int indegree[32001]; bool visited[32001]; int Count;   void DFS(int here) {     cout << here << " ";     Count++;     visited[here] = true;     for (int i = 0; i < adj[here].size(); i++) {         int there = adj[here][i];         indegree[there]--;     }     for (int i = 1; i <= N; i++) {         if (!visited[i] && indegree[i] == 0)             DFS(i);     } }   int main() {     int a, b;     cin >> N >> M;     for (int i = 0; i < M; i++) {         cin >> a >> b;         adj[a].push_back(b);         indegree[b]++;     }       for (int i = 1; i <= N; i++) {         if(adj[i].size()>1)             sort(adj[i].begin(), adj[i].end());     }       while(Count < N)         for (int i = 1; i <= N; i++) {             if (!visited[i]&& indegree[i] == 0)                 DFS(i);         }       return 0; }   Colored by Color Scripter

cs

2)

#include<iostream>
#include<queue>
 
using namespace std;
 
const int MAX = 32001;
int N, M;
int Indegree[MAX];
vector<int> adj[MAX];
priority_queue<int, vector<int>, greater<int> > minHeap;
 
 
int main() {
    int a, b;
    cin >> N >> M;
    for (int i = 0; i < M; i++) {
        cin >> a >> b;
        //자신 이후에 들어오는 수들을 adj에 넣어준다.
        adj[a].push_back(b);
        //먼저 풀어야 하는 문제가 있는 노드의 진입차수를 1 증가시켜준다.
        Indegree[b]++;
    }
 
    //진입차수가 0인 노드들을 우선순위 큐에 넣어준다.
    for (int i = 1; i <= N; i++) 
        if (!Indegree[i]) minHeap.push(i);
    
    //모든 문제를 출력 할 때까지 반복한다.
    while (!minHeap.empty()) {
        //우선순위 큐 중에서 가장 작은 수를 출력한다.
        int printHere = minHeap.top();
        minHeap.pop();
        cout << printHere << " ";
        for (auto min : adj[printHere])
            if (--Indegree[min] == 0)
                minHeap.push(min);
    }
 
    return 0;
}
 

3. 참고

http://melonicedlatte.com/algorithm/2018/08/18/234125

https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html

질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!