jumpingz   6일 전

해당문제를  1 번에서 각 정점들로 갈 수 있는지 여부를 확인하고 2번부터 N번까지 각 정점에서 N번으로 갈 수 있는지를 

BFS 를 통해서 저장하고 테스트가 주어질떄마다 인덱스 정보를 보고 결과를 출력하는 방식을 선택했는데요

아무래도 정점개수와 간선개수가 어마무시하다보니 어떠한 입력을 사용해도 계속 시간초과가 발생하네요..

아래 주석친 영역을 수정해야 할 듯한데 다른 방법은 생각이 안나네요...

jh05013   6일 전

BFS를 "뒤집어서" 실행하면 각 정점에서 v로 갈 수 있는지를 볼 수 있습니다.

jumpingz   6일 전

머리가 멍청해서.. 계속 고민해봐도 어떻게 해야할지 모르겟네용... 어떤 의미인지 좀 더 자세하게 설명해주실수있으신지요 ㅠ

jh05013   6일 전

a에서 b로 가는 경로를 거꾸로 따라가면 b에서 a로 가는 경로가 됩니다. 즉 각 정점에서 N번으로 가는 경로가 있다면 거꾸로 갔을 때 N번에서 각 정점으로 가는 경로가 됩니다.

이제 문제는 거꾸로 된 경로를 찾는 것인데, 모든 간선을 뒤집으면 경로의 방향도 뒤집을 수 있습니다.

jumpingz   6일 전

아 그렇군요 정말 감사합니당

댓글을 작성하려면 로그인해야 합니다.