SCC. [2152]

[1. 문제 설명]

[2. 풀이 접근]

아래 문제와 유사하다.

이 문제에서 헷갈릴만한 부분을 몇가지 정리하면 아래와 같다.

S 에서 시작해서 T 에서 끝나야 한다.
=> 만약, S 와 T 가 같은 SCC 에 있다고 했을 때, S ~~~> T ~~~> Z 로 갈 수 있다고 했을 때,
Z 를 경유하지 않고 T 에서 끝나야 하는가?

1번 질문에 대해서 Z 경유 없이 T 에서 끝내야 한다면, 문제가 까다로워 질 수 있다.

같은 SCC 내에서 S 에서 T 까지 최대한 많은 도시를 경유해야하는 문제를 또 풀어야 하기 때문이다.

그러나 문제에서 같은 도시를 여러 번 방문 할 수 있다고 하였으며,

이 말은 곧 도시 T 역시 여러 번 방문 할 수 있다고 봐도 된다.

다음은 문제 풀이 시 메모리 초과가 발생한 부분이다.

SCC 컴포넌트를 노드로 하는 그래프는 DAG 이다.

위와 같은 특성때문에 그래프 내 모든 경로를 탐색 해 볼 수 있다.

다만, 이 문제에서 한 가지 실수한 부분은 방문한 도시 개수 비교 시 등호를 생략했던 부분이다.

등호를 생략하면 탐색 범위가 넓어진다.
경로 ... -> B -> K -> ... 와
경로 ... -> C -> K -> ... 에서 K 이후 경로는 같아질 것이므로, 둘 중 하나만 탐색해도 된다.

모든 그래프 탐색에서 코스트 비교 시 확실 히 큰 경우에만 탐색 범위에 추가하도록 한다.

전체 풀이 정리

모드 노드를 각각의 SCC 에 묶도록 한다.
S 와 T 가 같은 SCC 에 있다면 이 SCC 에 속한 노드 개수를 반환한다.
=> SCC Graph 관점에서 u -> v 로 갈 수 있지만, v -> u 로 다시 갈 수 없기 때문이다.
SCC 그래프를 만든다.
S 가 속한 SCC 에서 T 가 속한 SCC 로 가는 모든 경로를 탐색한다.

[3. 코드]

test_kernelv2