[programmers] Lv3. 여행경로 Javascript | DFS+재귀+clone | protect-me
🕊 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)
Lv3. 여행경로 Javascript
https://programmers.co.kr/learn/courses/30/lessons/43164
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 - 최초 작성
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]
}
- 제약조건 중 한가지만 보고 달려들지 말자.
- 제약조건을 모두 보고 로직을 세우는 연습.
- vertex를 clone을 해서 쓰는 문제는 처음 접함.
- 방향 그래프이면서 중복되는 value를 가지는 노드가 존재하는 그래프이기 때문에 매우 복잡하게 느껴짐.
- 재귀는 아직도 많이 서툴지만, DFS 재귀를 어떻게 써야할지 약간 감을 잡았다.
- 2021.08.12 - 최초 작성
댓글 환영
질문 환영
by.protect-me
Author And Source
이 문제에 관하여([programmers] Lv3. 여행경로 Javascript | DFS+재귀+clone | protect-me), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@protect-me/programmers-Lv3.-여행경로-Javascript-DFS재귀-protect-me저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)