[자바스크립트, js] 프로그래머스 여행경로

안녕하세요,

 

오늘은 난이도 3의 여행경로를 가져왔습니다. 요즘 많이 부족하다고 생각하는 BFS, DFS 관련된 문제들을 풀려고 하는데.. 생각보다 많이 어렵네요..

 

계속계속 반복해서 익숙해질때까지 열심히 해야죠..

 

쨋던, 풀었던 저의 주관적인 풀이를 공유하고자 합니다!

---

문제 설명

주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 "ICN" 공항에서 출발합니다.

항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요.

---

제한사항

• 모든 공항은 알파벳 대문자 3글자로 이루어집니다.
• 주어진 공항 수는 3개 이상 10,000개 이하입니다.
• tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다.
• 주어진 항공권은 모두 사용해야 합니다.
• 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.
• 모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.

---

입출력 예

tickets	return
[["ICN", "JFK"], ["HND", "IAD"], ["JFK", "HND"]]	["ICN", "JFK", "HND", "IAD"]
[["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]]	["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"]

---

우선 이 문제같은 경우에는

 

DFS를 사용해서 풀 수 있습니다! 하지만 이렇게 말하는 나는.. BFS로 풀다가 시간만 낭비했지.. ㅎㅎ..

 

우선 조건이 하나 있습니다. 지금의 경로와 티켓들의 시작 경로와 일치하는지를 확인해야 합니다. 만약 일치한다면, 다음 경로로 이동을 하게 됩니다. 모든 경로를 순회하는 리스트가 만들어 진다면 그 경로들을 대상으로 sort()를 통해 알파벳 순, 0번째 인덱스를 뽑아주면 됩니다.

 

하지만, 갔던 경로를 가면 안되니 중복으로 방문하는 것은 막아야 합니다. 저같은 경우에는, 기존의 tickets를 매번 방문한 index를 제거해주는 방식으로 중복을 방지하였습니다! 

 

function solution(tickets) {
  let queue = []
  const dfs = (startTarget, sliceTickets, routeTickets) => {
    if(sliceTickets.length > 0){
      sliceTickets.forEach(([start, end], index) => {
        if(startTarget === start){
          dfs(end, [...sliceTickets.slice(0, index), ...sliceTickets.slice(index+1)], [...routeTickets, startTarget])
        }
      })
    } else {
      queue.push([...routeTickets, startTarget])
    }
  }
  dfs("ICN", tickets, [])
  return queue.sort()[0];
}

이렇게 정리할 수 있습니다!

 

생각보다 많이 어렵지는 않았지만.. 역시 머리로 생각하는 내용을 코드화 하는건 많이 어려운 것 같습니다..

 

도대체 언제쯤 되어야 코딩테스트를 잘할 수 있을까요.. 오늘도 나는 감자다 감자...

 

다른 풀이들도 한번 방문해주세요~

 

한솔방울 깃허브

 

이상 감사합니다!!