[프로그래머스 Lv.3] 여행경로: JavaScript 알고리즘 풀이 with DFS (Feat. 얕복 깊복 이슈)

 

들어가며

요즘 알고리즘, 자료구조를 열심히 공부하고 있는데 그중 DFS/BFS 문제를 집중적으로 공략하고 있습니다.
 
아직 제가 재귀함수에 익숙하지 않기도 하고, 또 해당 문제는 사실 일반적인 DFS 문제이기는 한데, 얕복 깊복 개념 고려 안하고 막 풀었다가 예상과 다른 결과가 나와서 당황하게 되었던 문제입니다.
해당 이슈를 겪었던게 인상깊고 재밌어서 해당 문제 풀이를 포스팅하게 되었습니다.

---

풀이

코딩테스트 연습 - 여행경로 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

로직 설명

1. 사용한 티켓이거나 출발지가 다른 경우 X
2. 사용하지 않은 티켓이고 출발지가 동일한 경우 → 재귀함수 호출
   • 다음 출발지 순회
   • 만약 모든 티켓을 사용완료했다면, 경로 저장
   • 이전 노드로 되돌아갈 경우, 해당 노드의 값으로 초기화  
3. 경로 목록 중 문자열로 join 한 뒤 정렬해서 첫번째 경로 반환

코드

타입스크립트로 코드를 작성하였습니다.
 

 
 

해당 문제 풀이로 얻은 재미있는 지식

얕은 복사 & 깊은 복사

이때 얕복/깊복 문제로 헤맸던게 2가지 경우가 있는데요.
 
첫번째로는 라인 9:  stopover 를 paths 배열에 push 해줄때
두번째로는 라인 39~ (리팩토링으로 주석처리) : 경로 결과들을 가지고 문자열 순서로 값을 가져올 때 
 
둘 다 spread 연산자를 사용해서 해결하였습니다.

• 첫번째의 경우에는, 재귀함수가 돌아오면서 값이 자꾸 stopover 의 초기값의 배열을 리턴하는 경우를 겪었습니다.
  제 기억으로는 프로그래머스 Lv 2 피로도 문제 역시 DFS 를 사용하는 비슷한 유형의 문제인데, 이런 경우를 겪지 않았었습니다.
  해당 문제는 2차 배열이라서 이런 문제가 발생한 것 아닐까 싶어요. 
   메모리 할당 값을 snapshot 찍듯이 deep copy 로 값을 넣어주었더니 정상적으로 배열이 리턴되었습니다.
  
  추가적으로 더 살펴봐야하겠지만, 배열 자체를 push 할 때는 stopover 에 할당된 메모리를 얕은 복사로 처리하는구나로 이해하였습니다.
  재귀함수로 값을 반환할 때 변수는 mutable 하다는 것을 인지하고 처리할 때 더 주의해야겠다 느꼈습니다.
   

 
deep copy 시 정상적으로 배열 반환 (라인 10 실행 결과: 첫번째 로그)
2차 배열 그냥 Push 하는 경우 초기 값 반환 (라인 11 실행 결과, 2번째 로그)
 
 
 

• 두번째 케이스로는, 자바스크립트의 sort 메서드 관련해서 고려하지 못했었습니다.
  Array.prototype.sort() MDN 문서 를 확인해보니, 해당 메서드는 원본 배열을 변형합니다. 그래서 답이 정상적으로 리턴되지 않았는데요. 마찬가지로 spread 연산자로 deep copy 해서 해결하였습니다.
  문서를 읽어보니 JS toSorted() 를 사용해도 원본 배열을 변형하지 않아 동일한 결과를 반환한다고 합니다.
  개인적으로는 toSorted() 라는 메서드를 해당 문제를 풀면서 새롭게 알게되었습니다! 
   
  추가적으로, 해당 이슈를 고려해줄 필요 없도록 리팩토링해주었습니다.

 

마치며

사실 매번 메모리 얕복 깊복 문제는 알면서도 평상시에 생각없이 막 쓰다가 어 왜이러지? 이러는 순간들에 아! 이러는 경우가 많은 것 같아요.
해당 이슈가 매우 재밌고 나중에도 또 이런 삽질을 해서 미래의 제가 참고할 일이 생기지 않을까 하여 포스팅합니다. :)
언제든 피드백 환영하며, 읽어주셔서 감사합니다!