aayy4321   2년 전

난해하게 풀긴했는데 막히다가 통과한 부분 공유 합니다. 
처음에 
벨만포드 돌리고 n-1 번 이후에 증가하는 노드 변수에 저장해서 checknode라고 가정하고 

시작점 -> checknode
checknode -> 도착점 

경로 갈 수 있는지 체크(DFS or BFS)해서 풀었는데 17 퍼에서 막혔습니다.  
+ (수정) 저는 DFS/BFS로 경로 갈 수 있는지 체크 했는데  출발지점에서 중간지점 체크  (a1 = roadOk(start,i)) 부분은 벨만포드 돌리고 값이 초기값이 아니라면 도달할 수 있다고 판단할 수 있습니다. ( 중간지점에서 도착부분은  DFS/BFS 안쓰고 풀 수 있는지 모르겠네요..)
저 같은 알고리즘으로 푸신 분들 생각하셔야 할게 사이클이 여러개일 수 있다는 것입니다. 
 

preview

이렇게 사이클이 여러개인데 A사이클만 검사하게 된다면 B사이클이 도착노드에 미치는 영향을 무시하게 돼서 오답이 나올 수 있습니다.

twicedtna   2년 전

감사합니다!!!

그림그리신 부분을 예제 코드로 만들어서 사용했었는데 그것도 첨부합니다 (이동비용이 2인 부분이 A사이클, 0인 부분이 B사이클입니다)

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