[프로그래머스] 여행경로

https://school.programmers.co.kr/learn/courses/30/lessons/43164

코드 - 실패

function solution(tickets) {
    let answer = [];
    let hash = {}

    tickets.forEach(x => {
        if(hash[x[0]]){
            hash[x[0]].push(x[1])
            hash[x[0]].sort().reverse()
        }else{
            hash[x[0]] = [x[1]]
        }
    })

    let start = 'ICN'
    answer.push(start);

    while(Object.values(hash).join('')){
        start = hash[start].pop()
        answer.push(start)
    }
    return answer
}

BFS 써야할 것 같은데 쓰기 싫어서 그냥 직진으로다가 알파벳 순서 조건 맞춰서 풀었는데 런타임에러가 떴다.
질문하기를 보니까 알파벳 순서로 하면 막히는 경우가 있다고 했다.

코드 - 실패

function solution(tickets) {
    let answer = [];
    let hash = {}

    tickets.forEach(x => {
        if(hash[x[0]]){
            hash[x[0]].push(x[1])
            // hash[x[0]].sort().reverse()
        }else{
            hash[x[0]] = [x[1]]
        }
    })

    dfs(hash, 'ICN', answer, ['ICN']);



    return answer.filter(x=>x.length==tickets.length+1)
    				.sort()[0]
}

function dfs(hash, start, answer, course){


    if(!hash[start]){
        answer.push([...course])
        return;
    }
    let tmp;
    for(let i of hash[start]){
        course.push(i)
        tmp = hash[start].filter(x=>x!=i)
        tmp = tmp.length==0?null:tmp
        dfs({...hash, [start]: tmp}, i, answer, course)
        course.pop();
    }    
}

DFS 함수 재귀를 돌면서 hash 객체에 대해서 방문한 공항을 제외시키기 위해 filter를 써서 날렸다.
날리는 과정에서 배열에 아무것도 남게 되지 않으면 배열 메소드가 하나도 작동을 안 했기에 미리 길이를 측정하고 배열에 아무것도 남게 되지 않으면 null을 반영하게 했다.
저번처럼 런타임에러는 안 나왔지만 테스트케이스 1번에서 틀렸다.

코테연습힌트 모음집을 참고해서 테스트케이스 1번의 경우를 확인했을 때

tickets	result
[["ICN", "AAA"], ["ICN", "CCC"], ["CCC", "DDD"], ["AAA", "BBB"], ["AAA", "BBB"], ["DDD", "ICN"], ["BBB", "AAA"]]	["ICN", "CCC", "DDD", "ICN", "AAA", "BBB", "AAA", "BBB"]

테스트케이스를 줘서 해보니까 얘도 틀렸다.
코드를 따라가보니까

    {
  ICN: [ 'AAA', 'CCC' ],
  CCC: [ 'DDD' ],
  AAA: [ 'BBB', 'BBB' ],
  DDD: [ 'ICN' ],
  BBB: [ 'AAA' ]
}
[ 'ICN' ]
ICN [ 'AAA', 'CCC' ]
{
  ICN: [ 'CCC' ],
  CCC: [ 'DDD' ],
  AAA: [ 'BBB', 'BBB' ],
  DDD: [ 'ICN' ],
  BBB: [ 'AAA' ]
}
[ 'ICN', 'AAA' ]
AAA [ 'BBB', 'BBB' ]
{
  ICN: [ 'CCC' ],
  CCC: [ 'DDD' ],
  AAA: null,
  DDD: [ 'ICN' ],
  BBB: [ 'AAA' ]
}

AAA에서 BBB로 가는 티켓이 두 장이 있는데 filter로 인해 한 장만 써야하는데 두 장 다 사라져버리는 문제가 있었다.

 function solution(tickets) {
    let answer = [];
    let hash = {}

    tickets.forEach(x => {
        if(hash[x[0]]){
            hash[x[0]].push(x[1])
        }else{
            hash[x[0]] = [x[1]]
        }
    })

    dfs(hash, 'ICN', answer, ['ICN']);



    return answer.filter(x=>x.length==tickets.length+1)
    		.sort()[0]
}

function dfs(hash, start, answer, course){

    if(!hash[start]){
        answer.push([...course])
        return;
    }
    let tmp;
    for(let i=0;i< hash[start].length;i++){
        course.push(hash[start][i])
        tmp = hash[start].filter((_, idx)=>idx!=i)
        tmp = tmp.length==0?null:tmp
        dfs({...hash, [start]: tmp},
        					hash[start][i], answer, course)
        course.pop();
    }    
}

DFS 안의 for문을 for of가 아니라 index로 조작함으로써 filter 대상을 원소가 아닌 index로 바꿨다. 그랬더니 중복이 같이 날라가던 문제가 해결됐다.