17412번 - 도시 왕복하기 1
알고리즘이 그렇게 어려운 것이 아니라고 생각해 dfs로 풀었는데 틀렸다고 나요네요..
한 경로를 지났으면 다시 지날 수 없단 얘기는 그 경로는 이제 계산하지 않아도 된다는 얘기 아닌가요?
조언 구해봅니다..!
이 문제는 DFS 문제가 아니라 MCMF 문제입니다.
아예 접근법이 달랐군요.. 감사합니다 그걸 봐야겠네요!
저도 dfs로 접근하여 풀었는데 틀렸습니다. 한번 방문한 정점은 다시 지나지 않는다. 라는 말에서 방문한 정점 체크를 통해 그 정점을 통한 길은 더 이상 보지 않는다고 생각했습니다.
아직도 어떤 부분에서 틀리는지 이유를 모르겠습니다... 혹시 가능하시다면 답변 부탁드립니다...ㅠ
이미 방문한 정점을 다시 방문하지 않는다가 아니라,
이미 방문한 간선을 다시 방문하지 않는다가 문제의 조건이 아닐까요..
댓글을 작성하려면 로그인해야 합니다.
testtest4 4년 전
알고리즘이 그렇게 어려운 것이 아니라고 생각해 dfs로 풀었는데 틀렸다고 나요네요..
한 경로를 지났으면 다시 지날 수 없단 얘기는 그 경로는 이제 계산하지 않아도 된다는 얘기 아닌가요?
조언 구해봅니다..!