공부정리

A->B 가는 경로중에 C1,C2,,,,Ck를 순서 상관없이 모두 방문하는 경로의 수를 출력하는 문제다.

별 수를 다 써봤다.

  1. dfs를 돌려서 만족하는 경로의 간선만 남기는 방법을 사용했지만 dfs를 돌리며 간선을 참고할 때 참고하는 순서에 따라 대참사가 발생하는 경우가 있었다.

  2. bfs를 통해 check배열을 동시에 넘겼으나 실패.(정답의 방법을 이용하면 통과 가능할 것 같다)

결국 구글링을 해서 초고수님의 코드를 분석해 보니 답이 보이더라.

일단 해당 그래프에서 사이클이 없고 I,J도시 사이에 도로는 최대 하나만 있다는 점이 중요하다.

그리고 A->B로 가는 도중에 Cn을 방문하는 경우를 살펴보면, A에서 중간지점 D까지 갈 때 여러가지 3가지 경로가 있다고 가정했을 때

  경로 1을 통해서는 C1,C2,C3를 방문하고

  경로 2를 통해서는 C2

  경로 3을 통해서는 C3를 방문한다고 하자.

그럼 경로 2,3은 다 버려도 된다. 왜냐하면 사이클이 없기 때문에 경로2,3 -> D 를 통과해서 B까지 가는 경로를 구할 경우

  경로2의 경우에는 C1,C3을

  경로3의 경우에는 C1,C2를 방문할 기회가 아예 없기 때문이다.

이건 결국 어떤 Cn을 지나왔는지 기록할 필요도 없게 만드는데, 들렀던 Cn의 갯수를 저장하고 위상정렬을 진행하는 도중

경로 a를 이용해서 경유지 D에 도달할 때 2개의 Cn을 지나고 경로의 수가 4

경로 b를 이용해서 경유지 D에 도달할 때 1개의 Cn을 지나고 경로의 수가 7이라면

경로 b의 경우의 수는 다 버리고 경로 a의 값을 취해야 한다는 걸 의미한다.

또한 이렇게 위상정렬을 진행하다가 B에 도달했을 때 cnt[B](=지나온Cn갯수) == Cn.size 와 같을 때만 경로가 존재하고, 아닌경우에는 경로가 없다는 말이 된다.

나중에 문제 까먹고 다시 보면 풀 수 있을지 모르겠다.