프로그래머스(여행경로).md

프로그래머스(여행경로)

---

//통과한 코드
function solution(tickets) {
    let result = []
    let ans = []
    let tickets_len = tickets.length
    let visited = Array(tickets.length).fill(0)
        const dfs=((start)=>{
            //ticket을 모두 사용한 경우
        	if(ans.length==tickets_len){
                ans.push(tickets[start][1])
                let tmp = ans.slice()
                result.push(tmp)
                ans.pop(tickets[start][1])
                return
        	}
            //백트래킹 구현
            for(let i=0;i<tickets_len;i++){
                if(visited[i]==0 && tickets[start][1]===tickets[i][0]){
                    visited[i] = 1
                    ans.push(tickets[i][0])
                    dfs(i)
                    visited[i] = 0
                    ans.pop()
                }
       		 }
    	})
    for(let i=0;i<tickets.length;i++){
        if(tickets[i][0]==='ICN'){
            visited[i] = 1
            ans.push(tickets[i][0])
            dfs(i)
            console.log(result)
            visited[i]=0
            ans.pop()
        }
    }
    //console.log(result)
    return result.sort()[0]
}

//가장 처음에 제출했던 코드
function solution(tickets) {
    let result = []
    let ans = []
    let tickets_len = tickets.length
    let visited = Array(tickets.length).fill(0)
        const dfs=((start)=>{
        let flag = 0
        for(let i=0;i<tickets_len;i++){
            if(visited[i]==0){
                flag = 1
                break
            }
        }
        if(!flag && ans.length===tickets_len){
            ans.push(tickets[start][1])
            result.push(ans)
            ans = []
            return
        }
        for(let i=0;i<tickets_len;i++){
            if(visited[i]==0 && tickets[start][1]===tickets[i][0]){
                visited[i] = 1
                ans.push(tickets[i][0])
                dfs(i)
                visited[i] = 0
            }
        }
    })
    for(let i=0;i<tickets.length;i++){
        if(tickets[i][0]==='ICN'){
            visited[i] = 1
            ans.push(tickets[i][0])
            dfs(i)
            console.log(result)
            visited.fill(0)
            ans=[]
        }
    }
    //console.log(result)
    return result.sort()[0]
}

---

dfs와 백트래킹 개념을 같이 사용해야 하는 문제였다. 굉장히 오래 애를 먹었는데 다차원 배열에 대한 특징을 까먹었기 때문이다.

let result = []
let ans = [1, 2, 3]
result.push(ans)
console.log(result) //[[1, 2, 3]]
ans[1] = 123
console.log(result) //[[123, 2, 3]]

let result = []
let ans = [1, 2, 3]
result.push(ans)
console.log(result) //[[1, 2, 3]]
ans.length = 0
console.log(result)//[[]]

배열 안에 배열을 넣는 모양으로 코드를 구상하였고, 그런 식으로 구현하였다. 여러 개의 테스트 케이스들을 모두 통과했기 때문에 문제가 없을 것이라 생각했지만 실제로 제출하면 계속해서 1번 테스트케이스에서 틀렸다는 답안을 받았다.

테스트케이스에서는 문제를 일으키지 않았지만 조금 더 큰 배열이 들어오게 되면 이 깊은 복사에서 문제를 일으켰던 것 같다.

때문에 이 코드를

result.push(ans)

let tmp = ans.slice()
result.push(tmp)

이런 식으로 수정하여 해결하였다. slice 메서드를 사용하면 1차원 배열에 대한 깊은 복사를 수행할 수 있다.

또한, 백트래킹 개념을 구현하는 부분에서도 조금씩 문제가 있었다. 백트래킹 문제를 풀어본 적은 있지만 항상 갈 수 있는지 없는지만을 구하는 문제만을 풀어봤다보니 ans에 쌓인 값을 pop 해야 한다는 생각은 하지 못했다. visited 배열만을 수정해 놓고는 백트래킹을 구현했다 생각해버렸다.

또한, 이 문제를 해결하기 위해 다른 사람들의 코드를 보면서 재밌는 모양을 보았다

let visited = []
let ans = []

const dfs = (()=>{
 	~~~~
})

function solution(tickets){

}

내가 C++로 dfs를 풀 때와 모양이 굉장히 유사하다. 항상 dfs 함수를 밖으로 빼자니 파라미터가 너무 많아지고, dfs를 안으로 넣자니 코드 자체의 가독성이 너무 떨어진다는 느낌을 많이 받아왔다. 앞으로는 이 모양 처럼 큰배열, 자주 쓰이는 배열은 전역에 선언해두고 사용해야겠다.

---

💦느낀점

다차원 배열을 다룰 때는 항상 조심해야 한다. 특히 이 경우처럼 배열에 배열을 넣는 경우 깜빡할 가능성이 높을 것 같다. 반드시 배열에 배열을 넣을 때는 넣어야하는 배열을 깊은 복사해준 다음에 그 복사본을 배열에 넣어야 한다.... 거의 3시간 삽질해서 아마 안 까먹을 것 같다..