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

코딩테스트 연습 - 여행경로 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

---

📚 난이도 : Level 3

 

💡 풀이 과정 :

굉장히 시행착오가 많았던 문제...

 

일단 코드를 좀 더 간단하게 작성하기 위해서는

주어진 tickets배열을 객체 형태로 변환해주는 것이 편하다. (아래와 같은 형태)

const graph = {};
    for(const [a,b] of tickets){
        if(graph[a] === undefined) {
            graph[a] = [];
        }
     graph[a].push(b);
}

 

왜냐하면 배열 그대로 이용하면 전체 배열 순회가 굉장히 많아지기 때문도 있고,

dfs라고 하면 visited 배열을 선언을 해줘야 될 것 같은데 주어진 tickets를 객체형태로 변환을해주면

방문한 티켓에 대해 pop()을 해주면 되기 때문에 visited 배열 선언도 필요가 없다.

 

그리고 주어진 조건에서 중요한 점은 알파벳 순으로 방문을 해야한다는 것이다.

알파벳 순으로 방문하기 위해 나는 graph 객체의 값들을 "역순" 으로 정렬해주었다.

그 이유는, answer에 들어갈 때는 graph[src] 배열에서 방문할 요소를 pop()을 해주기 위해서는 역순으로 정렬되야한다.

예를들어 graph[src] = [ 'bbb', 'aaa'] 이면 grpah[src].pop()을 하면 'aaa'가 들어가는 형식(알파벳순으로 들어감)

 

 

위와 같이 선언을 해주고 stack을 이용해 dfs를 돌려주면 예외가 발생한다.

"ICN" 부터 방문하기 때문에 알파벳순으로 방문했을 시 다 방문하지 못하는 경우가 생긴다 ! !

그 경우를 생각하지 않는다면 테스트케이스 1번에서 틀리다고 나올것이다.

tickets = [["ICN", "AAA"], ["ICN", "CCC"], ["CCC", "DDD"], ["AAA", "BBB"], ["AAA", "BBB"], ["DDD", "ICN"], ["BBB", "AAA"]];

ICN 다음 AAA를 먼저방문하면 모든 티켓을 방문하지 못한다.

 

위에 대한 해결방법으로 처음에 나는

icn 다음에 방문할수 있는 지역들에 대한 인덱스를 지정을 해두고 

dfs를 돌린다음 answer.length === tickets.length+1 이 아닐 때 다음 인덱스를 방문하는 식으로해줬는데

이 방법도 문제가 있는게 icn다음에 방문할 수있는 지역이 굉장히 많다면

나올수 있는 경우의 수는 n!이다. 그렇기에 첫번째에 대해서만 고려를 하면 안된다는 것. 

글로 설명하니 내가 봐도 알아들을  수 내용인데 뭐튼 위는 틀린 내용이니까 지나가고

 

바로 stack에서 pop()한 결과를 answer에 넣는 것이 아닌

계속 스택에 쌓아놨다가 그 다음으로 방문할 수 없을 때 pop을 계속해준다.(pop한건 answer에 push)

그러면 결국에 icn이 남게되고 icn에 대해 또 dfs를 돌릴 수 있게된다.

결국 모든 티켓을 방문할 수 있다.

 

추가로 코드 이해가 안 갈 수가 있어서 

tickets = [["ICN", "AAA"], ["ICN", "CCC"], ["CCC", "DDD"], ["AAA", "BBB"], ["AAA", "BBB"], ["DDD", "ICN"], ["BBB", "AAA"]];

이 경우에 대해 stack 형태를 보여드리면

[ 'ICN' ] [ 'ICN', 'AAA' ] [ 'ICN', 'AAA', 'BBB' ] [ 'ICN', 'AAA', 'BBB', 'AAA' ] [ 'ICN', 'AAA', 'BBB', 'AAA', 'BBB' ] [ 'ICN', 'AAA', 'BBB', 'AAA' ] [ 'ICN', 'AAA', 'BBB' ] [ 'ICN', 'AAA' ] [ 'ICN' ] [ 'ICN', 'CCC' ] [ 'ICN', 'CCC', 'DDD' ] [ 'ICN', 'CCC', 'DDD', 'ICN' ] [ 'ICN', 'CCC', 'DDD' ] [ 'ICN', 'CCC' ] [ 'ICN' ]

위와 같이 되어 stack에서 pop된게 answer에 들어간다.

answer는 거꾸로 들어갔기에 나중에 reverse를 해준다.

 

 

level 3짜리 문젠데 왜캐 어려운지 ㅠ 

덕분에 이문제로 좀 dfs를 정해진 방식으로만 사용하지 않고 응용하여 풀 수 있는 방법도 알게된 느낌이다.

 

 

코드 :

function solution(tickets) {    
    const graph = {};
    for(const [a,b] of tickets){
        if(graph[a] === undefined) {
            graph[a] = [];
        }
        graph[a].push(b);
    }

    for(const key in graph){
        graph[key].sort((a, b) => a > b ? -1 : 1);
    }

    const stack = ['ICN'];
    const answer = [];

    while(stack.length>0){
        console.log(stack);
        const st = stack[stack.length-1];
        if (graph[st] && graph[st].length > 0) {
           stack.push(graph[st].pop());
        } else { 
            answer.push(stack.pop());
        }
    }

    return answer.reverse();;
}