문제

문제 링크

문제 접근

  • 이 문제에서 문제집을 잘 풀기 위해서는 푸는 순서가 정해져 있다.
  • 먼저, 먼저 풀 문제가 없어진 친구에 대해서는 먼저 풀되 먼저 풀 문제가 없어진 문제가 여러개인 경우 index 작은 문제(쉬운 문제)를 먼저 푼다.
  • 먼저 풀어야 하는 문제가 있다는 점에서 문제간에 위존성이 있기에 이 문제는 위상정렬로 풀 수 있을 거라는 느낌이 왔다.
  • 위상정렬로 진행하되 incoming edge의 개수가 같은 문제에 대해서는 index가 작은 친구가 먼저 풀리도록 다음과 같이 힙을 사용하였다.
priority_queue<pii, vector<pii>, greater<pii> > pq;
//incomming edge 개수, index
for(int i = 1; i < n + 1; i++)pq.push(pii(in[i], i));

코드

#include <cstdio>
#include <vector>
#include <queue>
#define pii pair<int, int> 
#define IN first
#define I second
using namespace std;

int in[32001], visited[32001], n, m, v1, v2;
vector<vector<int> > edge;


int main(){
    
    scanf("%d %d", &n, &m);
    edge = vector<vector<int> >(n+1);
    for(int i = 0; i < m; i++){
        scanf("%d %d", &v1, &v2);
        in[v2]++;
        edge[v1].push_back(v2);
    }
    priority_queue<pii, vector<pii>, greater<pii> > pq;
    for(int i = 1; i < n + 1; i++)pq.push(pii(in[i], i));
    while(!pq.empty()){
        pii top = pq.top(); pq.pop();
        if(visited[top.I])continue;
        visited[top.I] = 1;
        printf("%d ", top.I);
        int top_in = top.IN, top_i = top.I;
        for(int i = 0; i < edge[top_i].size(); i++){
            int next_i = edge[top_i][i];
            in[next_i]--;
            pq.push(pii(in[next_i], next_i));
        }
    }
}

느낀점

  • 위상정렬을 쓸 타이밍을 이제 좀 알아가고 있는 것 같다.