원탐과 원복

Question

강의 듣고 DFS랑 무슨 차이인지 한번에 정리가 안되어 글 남겨봅니다.. DFS는 경로에 대해 완전 탐색하는 것은 맞으나 그 경로의 모든 경우의 수를 탐색하는 것은 아니다. 왜냐하면 앞서 지나간 자리에는 visited가 걸려있으므로 목적지를 찍은 후 재귀로 중간 부분으로 돌아온다면 다른 경로로 진입했을 시 visited가 걸려있을 수 있고 어쩌면 목적지에 도달할 수 없을 수도 있다. 완탐과 원복에서는 목적지까지 도달한 후 왔던 경로에 대해 방문 처리를 원복하기 때문에 목적지로 도달하는 모든 경로의 경우의 수를 가져갈 수 있다. 따라서 코스트가 더 많이 요구되는 것은 완탐과 원복하는 것이며, 즉 단순히 원하는 목적지만을 탐색하는 것을 목표하고자 한다면 DFS. 모든 경우의 수를 확인하여 최소, 최대 값을 원한다면 완탐과 원복을 사용하자. 라고 이해했는데 뭔가 잘못 이해한 것 같습니다. 하지만 그걸 몰라서 질문을 잘 못하겠네요.. 답변 주신다면 감사하겠습니다.

큰돌 · Answer

안녕하세요 mch님 ㅎㅎ DFS는 경로에 대해 완전 탐색하는 것은 맞으나 >> 아닙니다. 그저 깊이우선 탐색에 불과합니다. 보통 visited를 걸어서 방문한 정점은 다시 방문하지 않도록 합니다. 예를 들어 a - b - c - d 라고 했을 때 a, b, c, d 이렇게 탐색하지 a b c b d 이렇게 방문한 정점을 다시 방문하지는 않습니다. 경로라는 말이 좀 헷갈릴 수가 있는데 연결된 노드들을 모두 탐색하긴 하지만 모든 경로 a, b, c / a, b, d를 다 탐색하지는 않습니다. 완탐과 원복에서는 목적지까지 도달한 후 왔던 경로에 대해 방문 처리를 원복하기 때문에 목적지로 도달하는 모든 경로의 경우의 수를 가져갈 수 있다. >> 앞서 설명한 예제에서 a b c b d 이런식으로 탐색하는게 완탐입니다. 문제의 정의에 따라 다른데 예를 들어 a부터 시작해 끝점까지 가는 경우의 수를 구한다라고 했을 때 a, b, c, d이렇게 탐색하면 안되겠죠? a - b - c a - b - d 라는 경우의 수가 필요한 것이기 때문에 a b c b d 이런식으로 탐색해야 합니다. 따라서 코스트가 더 많이 요구되는 것은 완탐과 원복하는 것이며, >> 네 맞습니다. 기본적으로 단순 dfs보다는 정점을 더 탐색하므로 시간이 더 많이 들어 코스트가 더 많이 드는게 맞습니다. 즉 단순히 원하는 목적지만을 탐색하는 것을 목표하고자 한다면 DFS. 모든 경우의 수를 확인하여 최소, 최대 값을 원한다면 완탐과 원복을 사용하자. >> 네 맞습니다. DFS는 깊이 우선탐색을 간단히 한다면.. 이라고 생각하시면 됩니다. 좀 더 정리를 해드리면 다음과 같습니다. 완전탐색 (Brute Force)과 원복 완전탐색은 모든 경우의 수를 탐색하는 방법, 경우의 수가 많을 때는 매우 비효율적일 수 있음. 이 때 dfs 등으로 구현됨. ex) 숫자조합, 암호해독 깊이 우선 탐색 (DFS, Depth-First Search) 깊이 우선 탐색은 한 경로를 최대한 깊게 탐색한 후, 다른 경로를 탐색하는 방법.하 나의 경우에 대해 깊이를 우선적으로 탐색. 재귀함수를 통해 구현, 연결된 모든 노드를 탐색하고자 할 때 유용 a, b, c, d / 방문한 정점을 다시 방문하지 않음. ex) 미로찾기 또 질문 있으시면 언제든지 질문 부탁드립니다. 좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :) 감사합니다. 강사 큰돌 올림.

mch473700 · Answer

답변 감사드립니다 이해할때까지 곱씹어 생각해보겠습니다