노드와 간선의 정보가 주어지고 노드 번호가 주어지면 "그 노드까지 이어진 최장 경로"를 찾는 문제로 생각할 수 있는 데, 그림의 간선 방향을 반대로 바꾸면 "시작노드가 주어지고 시작노드로부터 가장 긴 경로"를 찾는 문제가 될 거라고 생각했다.
하지만 위 알고리즘은 시간초과를 벗어날 수 없게되었다...
친구의 도움을 받아 백트래킹을 이용하면 풀 수 있다는 것을 알게 되었다.
한 노드를 잡고 그 노드까지 가는 최대 경로를 누적하면 목적지까지 가는 노드를 알 수 있다!
백트래킹이 뭔지 모르는 친구에게 백트래킹을 배웠다. 밤낮으로 더 열심히 문제를 풀어야겠다.
댓글 2개:
이문제 시간초과로 고생하고있는데
백트래킹이라는 말이 무슨말인가요??
저는 해당 노드까지의 최대값을 리턴해주는 재귀함수를 동적계획법으로 캐시사용해서 했는데...이것보다 빠른게 있는지 모르겟네요ㅜ
반갑습니다. 블로그 확인을 못해 답변이 늦었네요.
저는 "도착점→출발점"으로 역추적하듯이 진행했습니다. (출발부터 시작하면 도착으로 절대 가지 않는 불필요한 재귀가 생기기 때문)
재귀를 마치면서 현재까지의 최대값을 갱신하는 부분은 똑같습니다. 한 노드 S를 가리키는 노드 T가 있다면 S의 건설시간은 S의 delay + T까지의 delay 가 되겠네요. 여기서 T가 여러개인데, 가장 delay가 큰 T를 고르면 됩니다.
시간복잡도는 O(N^2) 정도 되보이네요.
설명을 잘 못해드린것 같아 죄송합니다. 댓글 감사합니다.
댓글 쓰기