난해하게 풀긴했는데 막히다가 통과한 부분 공유 합니다. 처음에 벨만포드 돌리고 n-1 번 이후에 증가하는 노드 변수에 저장해서 checknode라고 가정하고
시작점 -> checknode checknode -> 도착점
경로 갈 수 있는지 체크(DFS or BFS)해서 풀었는데 17 퍼에서 막혔습니다. + (수정) 저는 DFS/BFS로 경로 갈 수 있는지 체크 했는데 출발지점에서 중간지점 체크 (a1 = roadOk(start,i)) 부분은 벨만포드 돌리고 값이 초기값이 아니라면 도달할 수 있다고 판단할 수 있습니다. ( 중간지점에서 도착부분은 DFS/BFS 안쓰고 풀 수 있는지 모르겠네요..) 저 같은 알고리즘으로 푸신 분들 생각하셔야 할게 사이클이 여러개일 수 있다는 것입니다.
이렇게 사이클이 여러개인데 A사이클만 검사하게 된다면 B사이클이 도착노드에 미치는 영향을 무시하게 돼서 오답이 나올 수 있습니다.
aayy4321 2년 전 3
난해하게 풀긴했는데 막히다가 통과한 부분 공유 합니다.
처음에
벨만포드 돌리고 n-1 번 이후에 증가하는 노드 변수에 저장해서 checknode라고 가정하고
시작점 -> checknode
checknode -> 도착점
경로 갈 수 있는지 체크(DFS or BFS)해서 풀었는데 17 퍼에서 막혔습니다.
+ (수정) 저는 DFS/BFS로 경로 갈 수 있는지 체크 했는데 출발지점에서 중간지점 체크 (a1 = roadOk(start,i)) 부분은 벨만포드 돌리고 값이 초기값이 아니라면 도달할 수 있다고 판단할 수 있습니다. ( 중간지점에서 도착부분은 DFS/BFS 안쓰고 풀 수 있는지 모르겠네요..)
저 같은 알고리즘으로 푸신 분들 생각하셔야 할게 사이클이 여러개일 수 있다는 것입니다.
이렇게 사이클이 여러개인데 A사이클만 검사하게 된다면 B사이클이 도착노드에 미치는 영향을 무시하게 돼서 오답이 나올 수 있습니다.