여행경로 프로그래머스

링크

결국 정답은 재귀였다.
같은 재귀로 dfs를 시도했는데 성공한 이유는 무엇일까
데이터를 너무 자주 정렬하고, 자주 비교하며, 불필요한 작업이 있었다.
- 알파벳 순서를 맞추기 위해 초반 route에 대해 전부 알파벳 순서로 정렬하기
- 해당 티켓을 사용했는지 여부를 확인하기위해 사용한 많은 변수들
- 자주 배열을 복사
- 정답이 바로 나오지 않고 한차례 작업을 거쳐서 나오면서 시간과 자원을 사용.
- 자료구조가 제대로된 자료구조가 아니었다.
자료구조 map을 활용
- 일반 배열을 트리에서 탐색하기 용이하게 {출발지점:[도착하는 지점1,도착하는 지점2, …],…}으로 key,value를 정하여 map으로 변환
DFS는 재귀로
- 앞에서 만든 map을 활용
알파벳순서 확인은 완성된 경로가 있을때만 비교

입력 데이터를 dfs에서 빠르게 확인할 수 있게 map에 적용
- [[출발,도착],…]인 배열을 {출발:[도착1,도착2,…],…}으로 바로 다음 경로 찾기 수월하게 변환
dfs 재귀적용
- (start,map,len,route)를 입력받는다.
  - 시작지점, map, 전체 티켓갯수, 현재 지나간 경로
- 종료 조건
  - 티켓 갯수를 dfs로 지나면서 줄여서 0이될때 (모든티켓 사용) 현재까지 저장된 route 반환 - 성공적으로 완료
  - 다음 갈수있는 경로자체가 없을때(and 아직 티켓이 남았을때) [-1]반환 - 중간에 티켓이 끊겨 실패
  - 다음 갈수이쓴 경로의 티켓을 모두 사용(and 아직 티켓이 남았을때) [-1]반환 - 중간에 티켓을 전부 사용하여 실패
- 다음 dfs의 재귀로 넘길때
  - start는 다음 지나갈 경로 ex)도착1
  - map에서는 {start:[도착1,…]}에서 도착1을 간다면 도착1을 제거한 map을 넘김
  - len은 len-1
  - route는 도착1을 push하여 넘긴다.
- 최종 반환
  - 중간마다 실패시 [-1]이 오고 성공시 완성된 route가 온다.
  - 완성된 route에 대해서만 새로운 완성된 route가 올때, 서로 비교하여 알파벳이 더 빠른 경로를 최종 반환하도록 한다.

이 문제는 DFS시 map을 안쓰고, 복잡한 재귀를 사용하여 runtime에러가 걸린 문제이다.
실패가 뜨는 경우는 DFS가 제대로 동작하지 않는경우지만, runtime에러인 경우 너무많은 조건과 데이터 처리가 있는지 확인해야 했다.
예전부터 map을 안쓰고 배열을 map처럼 쓰는 않좋은 습관이 있어 코드가 복잡해졌고, dfs도 너무 복잡하게 구현해 코드를 다시 읽기도 어려웠다.
map으로 데이터를 처리하는데 간단하게 만들고, 재귀에서 불필요한 동작을 최소한으로 하면서 runtime에러를 잡았다.

let copy = new Map(JSON.parse(JSON.stringify(Array.from(source))))
//참고 https://stackoverflow.com/questions/8206988/clone-copy-a-map-instance