🕊 Link

Lv3. 여행경로 Javascript
https://programmers.co.kr/learn/courses/30/lessons/43164

🧑🏻‍💻 Code(javascript)

function solution(ts) {
  const list = []
  const DFS = (airport, ts, path) => {
    let newPath = [...path, airport];
    if (ts.length == 0) list.push(newPath)
    else {
      ts.forEach((t, i) => {
        if (t[0] === airport) {
          let clone = [...ts]
          const [[from, to]] = clone.splice(i, 1)
          DFS(to, clone, newPath)
        }
      })
    }
  }
  DFS("ICN", ts, [])
  return list.sort()[0]
}

💡 Solution

최종 코드(재귀 DFS)

참고

function solution(ts) {
  const list = [] // 티켓을 모두 소진하는 path를 담을 list
  const DFS = (airport, ts, path) => {
    let newPath = [...path, airport]; // 기존의 path에 airport를 새로 추가
    if (ts.length == 0) list.push(newPath) 
    // 아래에서 조건에 맞을 때마다 splice로 ts의 length를 줄일 예정
    // ts.length가 0이면 list에 newPaht를 push함
    else {
      // ts에 요소가 남아있을 경우, 
      ts.forEach((t, i) => { // ts의 남은 요소를 돌면서
        if (t[0] === airport) { // t의 출발지가 현재 출발지와 같을 경우
          let clone = [...ts] 
          // 클론을 하지 않으면 새로 생성되는 재귀함수마다 같은 ts를 참조하기 때문에 로직이 엉망이 됨
          const [[from, to]] = clone.splice(i, 1)
          // 현재 ts를 clone 한 후에 현재의 t를 잘라내고
          // 잘라내고 남은 clone(ts) 
          // 잘라낸 t의 to를 DFS에 다시 넣음
          DFS(to, clone, newPath)
        }
      })
    }
  }
  DFS("ICN", ts, [])
  return list.sort()[0]
}

1차 코드(실패)

1, 2번 테스트를 실패.
갈 수 있는 경로 중 알파벳 순 첫번째 노드로만 가는 로직.
위와 같이 했을 경우, 티켓을 모두 소진하지 못하는 케이스가 있기 때문으로 실패한 것으로 판단.

function solution(ts) {
  const l = ts.length
  const v = new Array(l).fill(false)
  const q = []
  const answer = ["ICN"]
  q.push("ICN")

  while (q.length) {
    let cur = q.shift()
    let tempForSort = []
    ts.forEach((t, i) => {
      const [from, to] = t
      if (cur == from && !v[i]) tempForSort.push({ to, index: i })
    })
    tempForSort.sort((a, b) => a.to < b.to ? -1 : a.to > b.to ? 1 : 0);
    if (tempForSort.length > 0) {
      answer.push(tempForSort[0].to)
      q.push(tempForSort[0].to)
      v[tempForSort[0].index] = true
    }
  }
  return answer
}

🔁 복습 코드

function solution(tickets) {
  const routeList = []
  const dfs = (from, tickets, route) => {
    let newRoute = [...route, from]
    if (tickets.length === 0) routeList.push(newRoute)
    else {
      tickets.forEach((ticket, index) => {
        if (ticket[0] === from) {
          let clone = [...tickets]
          const [[ticketFrom, ticketTo]] = clone.splice(index, 1)
          dfs(ticketTo, clone, newRoute)
        }
      })
    }
  }
  dfs("ICN", tickets, [])
  return routeList.sort()[0]
}

👨🏻‍💻💭 Self Feedback

• 제약조건 중 한가지만 보고 달려들지 말자.
• 제약조건을 모두 보고 로직을 세우는 연습.
• vertex를 clone을 해서 쓰는 문제는 처음 접함.
• 방향 그래프이면서 중복되는 value를 가지는 노드가 존재하는 그래프이기 때문에 매우 복잡하게 느껴짐.
• 재귀는 아직도 많이 서툴지만, DFS 재귀를 어떻게 써야할지 약간 감을 잡았다.

• 2021.08.12 - 최초 작성

댓글 환영 질문 환영
by.protect-me