[백준][C++] 1766번: 문제집 <210>

직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다.

 

1766번: 문제집

생각의 흐름

"일의 순서를 정해야 한다" 라는 점에서 위상정렬이 먼저 생각났다.

여기서 위상정렬의 개념을 설명하지는 않겠다. 먼저 위상정렬에 대한 글을 읽어보기를 권정한다.

 

입력으로 다음과 같은 input을 받는다고 해보자.

4 2
4 2
3 1

4는 2를 먼저 풀어본 후 푸는 것이 좋으며, 3또한 1을 먼저 풀어본 다음 푸는것이 좋다.

 

따라서 간선이 4 -> 2, 3 -> 1 과 같은 방향그레프가 형성된다. (위상정렬은 단방향그레프 DAG 에서 가능하다)

따라서 진입 차수 inDegree[]를 생가해 보면,

inDegree[1] = 1

inDegree[2] = 1

inDegree[3] = 0

inDegree[4] = 0 이 된다.

 

따라서 진입 차수가 0인 3, 4 부터 우선순위 큐(PQ)에 담아 준다.

참고로 우선순위 큐는 오름차순 으로 사용해야 한다. 더 작은 수가 먼저 해결되어야 하기 때문이다.

 

따라서 맨 처음 우선순위 큐에는 다음과 같이 담기게 된다.

PQ : [3, 4]

 

여기서 3를 뽑은 후, 3과 연결된 정점의 진입차수를 -1 씩 적용시켜 준다.

이때 진입차수가 0이 되는 정점은 PQ에 추가시켜준다. 우리의 예시에서는 1의 진입차수가 1에서 0으로 변경되니 추가해준다.

PQ : [1, 4]

 

다시 1을 뽑아 반복하면

PQ : [4] 와 같아진다.

여기서 4를 뽑은 후 연결되 있는 정점인 2를 추가해 주면 다음과 같다.

 

PQ : [2]

다시 2를 뽑아 출력하면 끝난다.

 

나의 코드

#include <bits/stdc++.h>
using namespace std;
#define MAX 32001

int N, M;
int inDegree[MAX];
vector<int> Problem[MAX];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> M;
    for(int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        Problem[a].push_back(b);
        inDegree[b]++;
    }

    priority_queue<int, vector<int>, greater<int>> pq; // 내림차순
    for(int i = 1; i <= N; i++) {
        if(inDegree[i] == 0) {
            pq.push(i);
        }
    }

    vector<int> res;
    for(int i = 1; i <= N; i++) {
        if(pq.empty()) {
            break;
        }
        int node = pq.top();
        pq.pop();
        cout << node << " ";

        for(int i = 0; i < Problem[node].size(); i++) {
            int nextNode = Problem[node][i];
            inDegree[nextNode] -= 1;
            if(inDegree[nextNode] == 0) {
                pq.push(nextNode);
            }
        }
    }

    return 0;
}