[백준/C++] 문제집 (No. 1766)

 

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 위상정렬을 이용하고, 어떤 경우에 문제를 빨리 출력할지 구분하면 쉽게 해결할 수 있는 문제다.

 

조건에 따르면 더 쉬운 문제를 먼저 풀 수 있다면 먼저 풀어야 한다.

그러므로 1번 문제부터 사전에 풀어야 하는 문제가 몇 개인지 파악한다.

 

이제 위상정렬을 떠올리면, i번 문제를 풀 수 있는 경우 i번 문제를 풂으로써 i번째를 사전에 풀어야하는 문제들은 사전에 풀 문제가 1개씩 줄어든다는 사실을 알 수 있다.

 

이를 이용해 for 문으로 1번 문제부터 사전에 풀어야 하는 문제가 0인지 미리 풀어야 하는 문제가 있는지 파악한다.

 

만약 i번째 문제가 사전에 풀어야 하는 문제가 없다면, 그 문제를 해결한다.

그리고 i번째 문제를 풀었으므로 i번째 문제를 사전에 풀어야 하는 문제들에 대해 모든 사전 문제를 풀었는지 검사한다.

 

검사한 값이 0이라면(더 이상 풀어야하는 사전문제가 없다면) 그 문제를 풀 수 있다는 뜻이다.

이제 for문에서 i+1번째 문제를 풀 수 있는지 검사할 차례지만, 여기서 i번 문제를 풂으로써 i+1보다 더 쉬운 문제를 풀 수 있는 경우가 생길 수 있다.

 

그러므로 이러한 경우를 체크하기 위해 priority_queue를 이용해 i번째 문제를 풂으로써 풀 수 있는 문제들을 삽입한 뒤, priority_queue의 가장 쉬운 문제와 i+1번째 문제를 비교해 더 쉬운 문제를 먼저 풀도록 코드를 구현했다.

 

이렇게 for문으로 탐색하는 경우와 사전 문제가 없어짐으로써 더 쉬운 문제를 풀 수 있는 경우를 비교를 통해 구분하도록 하면 문제를 쉽게 해결할 수 있다.

 

 

 

​

[아이디어 정리]

1. 위상정렬을 이용해 사전에 풀어야 하는 문제들을 파악하고, 그래프로 저장한다.
2. for문으로 가장 쉬운문제부터 풀 수 있는지 확인한 뒤 i번째 문제를 풀 수 있다면, i번째 문제를 사전에 풀어야하는 문제들의 사전문제 수를 1씩 줄인다.
3. 만약 i번째 문제를 풂으로써 풀어야하는 사전문제의 수가 0이 되는 수들이 있다면, 그 수들을 priority_queue에 넣은 다음 i+1번째 문제와 priority_queue의 가장 쉬운 문제를 비교해 어떤 문제를 더 먼저 풀 지 선택한다.

 

 

 

Code

 

 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int N, M;
    cin >> N >> M;
    int st, ed;
    vector<int> cnt(N + 1, 0);
    vector<vector<int>> graph(N+1);
    for (int i = 0; i < M; i++) {
        cin >> st >> ed;
        cnt[ed] += 1;
        graph[st].push_back(ed);
    }
    priority_queue<int, vector<int>, greater<int>> q;
    
    for (int i = 1; i <= N; i++) {
        if (cnt[i] == 0) {
            cout << i <<" ";
            cnt[i] = -1;
            for (int j = 0; j < graph[i].size(); j++) {
                cnt[graph[i][j]] -= 1;
                if (cnt[graph[i][j]] == 0) {
                    q.push(graph[i][j]);
                    cnt[graph[i][j]] = -1;
                }
            }
        }
        while (!q.empty() && q.top() <= i) {
            int k = q.top();
            cout << k << " ";
            q.pop();
            for (int j = 0; j < graph[k].size(); j++) {
                cnt[graph[k][j]] -= 1;
                if (cnt[graph[k][j]] == 0) {
                    q.push(graph[k][j]);
                    cnt[graph[k][j]] = -1;
                }
            }
        }
    }
    return 0;
}

 

---

위상정렬에 대한 개념을 알고 있으면 쉽게 풀 수 있는 문제였다.

처음에 i번 문제를 풂으로써 사전에 풀 수 있는 문제를 어떻게 파악할까 고민을 했는데, 비교로 쉽게 해결할 수 있었다.

최근에 바쁘다고 문제를 많이 못풀었네... ㅜㅜ

게임을 좀 줄여야 할텐데;

 

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