ndb796
commented
3 years ago 안녕하세요, @kns2021 님!
우리는 일반적으로 완전 탐색(모든 경우의 수 탐색) 목적으로 DFS를 사용할 수 있습니다. 구체적으로는 깊은 복사를 사용하는 경우와 사용하지 않는 경우로 나눌 수 있는데요.
① 깊은 복사(deep copy)를 사용하지 않는 경우
어떠한 배열에서의 탐색을 수행할 때, 배열(리스트)의 값이 바뀌지 않고 고정되는 경우라면 깊은 복사를 이용하지 않아도 됩니다.
② 깊은 복사(deep copy)를 사용하는 경우
일반적으로 코딩 테스트에서는 배열(리스트)의 값이 바뀔 수 있는 경우에 깊은 복사(deep copy)를 사용하면 편합니다. 깊은 복사를 사용하는 경우 배열의 크기가 작은 경우가 많습니다. 청소년 상어 문제의 경우 배열의 크기가 4 X 4라는 점을 기억해 주세요.
청소년 상어 문제에서 깊은 복사를 사용한 이유
청소년 상어 문제에서는 각 상태(state)마다 상어가 이동 가능한 상태가 여러 개입니다. 참고로 이 문제에서 하나의 상태(state)는 하나의 2차원 배열로 표현될 수 있습니다.
@kns2021 님께서 말씀해주신 대로, 상어가 먹는 경우의 수 중에서 최댓값을 구하는 문제이므로 각각 경우의 수마다 서로 다른 array를 참조하도록 해야 하므로 매번 깊은 복사(deep copy)를 진행한 것입니다. 배열의 크기가 4 X 4로 작은 크기이기 때문에, 매번 깊은 복사를 이용해도 메모리 초과 판정을 받지 않습니다.
좋은 질문 감사합니다. 나동빈 드림
안녕하세요 책 잘 보고 있습니다!! 여쭤볼 게 하나 있는데요.
dfs 탐색을 할때 deepcopy 를 사용해서 깊은 복사를 진행하였는데
보통 재귀를 사용할 때 관례적으로 깊은 복사를 사용하나요?
상어가 각각 다르게 먹는 경우의 수 중 최댓값을 구하는 문제여서 array에 영향이 없도록 매번 깊은 복사를 한다!
이렇게 이해하였는데 전 아직 dfs를 사용할 때 깊은 복사를 사용한 경험이 없어서 질문 드립니다.
깊은 복사를 사용하는 경우를 알려주실수 있나요?