티스토리 뷰
풀이
그래프 문제로 저는 풀이 방법이 잘 떠오르지 않아서 어려웠습니다.
처음 생각한 풀이로는 "집과 회사 각각을 시작점으로 완전 탐색을 진행하고, 겹치게 방문한 노드의 수를 세면 되겠다"라고 생각했습니다.
정리하면 다음과 같습니다.
visA: S -> T 과정에서 방문한 노드 표시
visB: T -> S 과정에서 방문한 노드 표시
visA ∩ visB를 만족하는 개수 = ans (오답)
문제의 조건에 출근길 경로에 S는 여러 번 등장해도 되고, 퇴근길 경로에 T는 여러 번 등장해도 된다. 이 조건을 만족하지 못해서 틀렸습니다.
DFS로 완전 탐색을 진행하였는데, 노드를 방문한 뒤 방문 체크를 하므로, S에서 출발 했다면 다시 S로 돌아올 수 없습니다. (예를 들면 문제 예시 1에서 1->4->1->2->3이 가능한 경로인데, 이 경로를 구하지 못합니다. 1이 이미 방문되었다고 표시되었기 때문에..)
따라서 전략을 바꿀 필요가 있습니다. 저는 이 전략을 떠올리기 힘들었습니다.
바꾼 전략은 다음과 같습니다.
임의의 노드 X에 대해
1) visA: S -> X : S에서 탐색을 시작하여 방문한 모든 노드 표시
2) visB: X -> T : X에서 T까지 탐색을 진행하며 방문한 노드 표시
1) + 2) => S -> T
3) visC: T -> X : T에서 탐색을 시작하여 방문한 모든 노드 표시
4) visD: X -> S : X에서 S까지 탐색을 진행하며 방문한 노드 표시
3) + 4) => T -> S
여기서 2)과 4)을 구할 때 테크닉이 필요합니다.
바로 역방향 그래프를 이용하는 것입니다.
결론부터 말해서 2)를 예시로 들어보겠습니다.
모든 X를 시작점으로 T까지 탐색을 하는 것이 아니라, T를 시작점으로 한 번만 가능한 경로를 완전 탐색을 하는 것입니다. 그렇게 되면 방문한 노드들이 X가 되겠죠?
역방향으로 구하지 않으면 어떻게 될까요?
X -> T의 경우 임의의 모든 X에서 탐색을 시작하여 T에 도달할 때까지 많은 노드들을 탐색하게 됩니다.
마찬가지로 X -> S의 경우 임의의 모든 X에서 탐색을 시작하여 S에 도달할 때까지 많은 노드들을 탐색하게 됩니다.
넉넉잡아 상한을 생각해본다면, 각 X가 모든 노드를 거쳐 S에 도달한다면 n*(n-1) = O(n^2)이 됩니다. n = 10^5이므로 시간 초과가 날 수 있겠죠.
visA와 visC는 정방향으로, visB와 vicD는 역방향으로 구한 후, visA ∩ visB ∩ visC ∩ visD를 만족하는 개수를 세어주면 정답이 됩니다.