[백준 1649] 택시 (C++)

1649번: 택시

 

조건

N개의 노드가 존재하고 노드들은 서로 단방향으로 연결되어 있다.

A라는 노드에서 출발해 다시 A노드로 돌아올 수 없다.

U -> V 연결이 있다면 V -> U 연결은 있을 수 없다.

A에서 B로 가야 한다.

가는 도중에 C1, C2 ... Cn 노드를 거쳐가야 한다. 이때 중간 노드의 방문 순서는 중요하지 않다.

 

요구사항

A에서 B로 가기 위한 경로의 수를 출력하라.

 

---

A에서 B로 가는 모든 경로를 탐색해보는 top-down DP로 풀려다가 도저히 안돼서 분류를 봤다ㅠ

위상 정렬이었다.

이 문제를 왜 위상 정렬로 풀어야 하는지 이해하는데만 해도 한참 걸렸다..

결국 구글링해서 풀이를 이해했다. 

 

 

우선 A에서 B로 가야한다.

그런데 주어진 중간 노드들을 모두 방문해야한다.

이때 방문 순서는 상관 없다고 한다.

 

핵심 포인트는 방문 순서가 상관없는 것이고, 경로의 순서도 중요하지 않고,

오직 경로의 개수만 중요하다는 점이다.

(만약 경로마다 순서를 출력하라고 하면 어떻게 하지;;)

 

지금까지 찾은 유효한 경로의 개수를 저장하는 배열을 Route라고 하자.

Route[A]는 시작점이므로 1부터 시작한다. (중요)

 

이제 BFS 탐색을 시작한다.

 

현재 노드가 중간 노드에 포함된다면

현재 노드의 중간노드 방문 숫자를 +1 해준다.

 

그리고 현재 노드와 연결된 이웃노드들의 정보를 갱신해주러 가자.

 

유효경로 : A에서 시작한 경로

 

만약 다음 노드까지의 중간노드 방문 숫자와 현재 노드까지의 중간노드 방문 숫자가 같다면

다음 노드의 유효경로 개수에 현재 노드의 유효경로 개수를 더해준다.

 

만약 다음 노드까지의 중간노드 방문 숫자보다 현재 노드까지의 중간노드 방문 숫자가 더 많다면

다음 노드까지의 유효 경로 개수는 현재 노드까지의 유효 경로 개수와 동일하다.

마찬가지로 다음 노드의 중간노드 방문 개수는 현재 노드의 중간노드 방문 개수와 동일해진다.

 

다음 노드의 간선을 하나 지우고, indegree가 0이 되었다면 큐에 추가한다.

 

여기까지 단순히 코드를 설명했다.

 

 

각 노드가 지금까지 지나온 중간 노드의 개수와 유효한 경로를 가질 수 있다는 특성 때문에

위상정렬을 사용해야 하는이유가 된다.

 

임의의 한 노드가 지나온 유효 경로의 갯수와 방문했던 중간 노드의 개수를 가지고 있다면

해당 노드가 가진 자식들은 이 정보를 그대로 활용할 수 있고, 해당 노드에 방문하는 새로운 노드들도 이 정보를 활용해서 정보의 갱신이 이루어질 수 있다.

따라서 해당 노드는 자신만의 위상을 가지고, 다른 노드들이 자신을 거슬러서 다른 노드를 탐색하는 것을 막아준다.

 

 

그래서 결국 B로 가는 유효 경로를 출력해야 한다.

B가 가진 정보 중에서 방문했던 중간 노드의 개수와 문제에서 주어진 중간 노드의 개수가 동일하다면

Route[B]를 출력하면 된다.

 

 

#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <cstring>
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;
 
int N, M, A, B, K;
vector<int> adj[1001];
set<int> mustVisit;
int visit[1001];
int route[1001];
int indegree[1001];
 
void input(){
    cin >> N >> M;
    int u, v;
    for(int i = 0; i < M; i++){
        cin >> u >> v;
        adj[u].push_back(v);
        indegree[v]++;
    }
    
    cin >> A >> B >> K;
    for(int i = 0; i < K; i++){
        cin >> u;
        mustVisit.insert(u);
    }
}
 
bool isInmustVisit(int node){
    if(mustVisit.find(node) != mustVisit.end()) return true;
    else return false;
}
 
void solve(){
    queue<int> que;
    route[A] = 1;
    
    for(int i = 1; i <= N; i++){
        if(!indegree[i]) que.push(i);
    }
    
    while(!que.empty()){
        int now = que.front();
        que.pop();
        
        // Cn 노드 방문
        if(isInmustVisit(now)) visit[now]++;
        
        for(int i = 0; i < adj[now].size(); i++){
            int next = adj[now][i];
            if(visit[next] == visit[now]){
                route[next] += route[now];
            }
            else if(visit[next] < visit[now]){
                visit[next] = visit[now];
                route[next] = route[now];
            }
            if(--indegree[next]== 0) que.push(next);
        }
    }
}
 
int main(){
    fastio
    input();
    solve();
    if(visit[B] == mustVisit.size()) cout << route[B];
    else cout << 0;
    
    return 0;
}