[백준] 1766번 문제집 (C++)

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

 

 

이 문제는 그래프의 선행 관계가 주어졌을때 3가지 조건을 고려하여 문제푸는 순서를 출력하는 문제이다.

 

1. N개의 문제를 다 풀어야 함

2. 먼저 푸는 것이 좋은 문제가 있으면, 먼저 푸는 것이 좋은 문제를 반드시 먼저 풀어야 함

(4 2)와 같은 관계가 주어졌을 때 4먼저 풀고 2를 풀어야함

3. 가능하면 쉬운 문제부터 풀어야한다.(가장 낮은 값 먼저 풀어야함)

 

 

따라서 방향 비순환그래프가 성립이 되기 때문에 위상정렬을 사용하여 순서들을 뽑아낸다 

이때 위상정렬을 수행할때 자료구조를 보통 큐를 사용하여 선입 선출구조를 만들어 내는데

 

이 문제에서는 가장 낮은 숫자를 먼저 푸는것이 이득이므로 최소힙을 사용하여 낮은 순서부터 푸는 관계를 만든다.

 

정답 코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"
#define MAX 1e9

struct coordinate {
    int x;
    string s;
    vector<int> v;
};

int dx[] = {-1, 0, 1, 0, 1, -1, -1, 1};
int dy[] = {0, 1, 0, -1, -1, 1, -1, 1};
int N, M;
int isDegree[32001];
bool visited[32001];
vector<vector<int>> v(32001);

void solve() {
    priority_queue<int, vector<int>, greater<int>> pq;
    vector<int> tmp;

    for(int i = 1; i <= N; i++) {
        if(isDegree[i] == 0) {
            pq.push(i);
        }
    }

    while(!pq.empty()) {
        int x = pq.top();
        tmp.push_back(x);
        pq.pop();

        for(auto it : v[x]) {
            if(--isDegree[it] == 0) {
                pq.push(it);
            }
        }
    }

    for(auto it : tmp) {
        cout << it << " ";
    }
}

void input() {
    cin >> N >> M;

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

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    input();
    solve();
}

 

 

회고록

처음엔 방문배열을 사용하여 구현을 했는데 4퍼에서 틀리고 질문 게시판을 보니 최소힙 관련 내용이 있어서

바로 감을 잡고 풀었다...

가장 낮은 문제를 푸는것의 문구를 보고 최소힙을 생각해낸다면 쉽게 풀 수 있는 문제라고 생각이든다.