3044번: 자전거 경주 준비하기

3044번: 자전거 경주 준비하기 - 위상정렬

N개의 마을이 M개의 일방통행 도로로 연결되어 있을 때

1번 마을에서 시작하여 2번 마을로 끝나는 경로의 수를 구하는 문제이다.

접근 방법은 다음과 같다.

1번 마을에서 X번 마을까지의 경로의 수는 X번 마을이 도착점으로 연결되어 있는 마을의 경로의 수의 합과 같다.

즉 X번 마을이 도착점으로 연결되어 있는 마을의 경로의 수를 모두 구한다면 이들을 합하여 구할 수 있을 것이다.

이는 그래프를 위상정렬한 순서대로 경로의 수를 구해주면 된다는 것을 알 수 있다.

먼저 1번 마을부터 2번 마을로 갈 수 있는 간선들만 모은 그래프를 다시 재생성 하여야 한다.

이유는 위상정렬은 사이클이 없는 방향 그래프(DAG)에서만 할 수 있는데

사이클이 있으면 무조건 inf를 출력해줘야한다고 생각하기 쉽지만

1번 마을과 2번 마을을 거치는 경로와 전혀 상관 없는 마을을 잇는 사이클은 의미가 없기 때문이다.

그러므로 1번 마을을 시작점으로 하여 DFS를 진행 한 뒤 도달 가능한 범위로 그래프를 재생성하고

이 때 2번 마을까지 도착 할 수 없다면 0을 출력한다.

도달 할 수 있다면 위상정렬 순으로 경로의 수를 다음 노드에 더해주며 이 때 이 재생성된 그래프에 사이클이 있어

2번 마을까지 도달하지 않는 경우는 inf일 경우이며 남은 경우에는 2번 마을까지의 경로의 수의 합을 구해주면 된다.

또한 마지막에 출력할 때 문제에서 숫자 뒤의 9자리까지만 출력하라 했으므로 경로를 더하는 중에 10^9을 넘어간다면

따로 그 노드에 체크를 해주어 다른 방법으로 출력하도록 하면 풀 수 있는 문제이다.