2025-01-08 TIL

아침 코딩 공부

주어진 항공권을 모두 이용하여 여행경로를 짜려고 한다. 항상 ICN 공항으로 출발한다. 항공권 정보가 담긴 2차원 배열 TICKET이 매개변수로 주어질 때 방문하는 공항 결로를 배열에 담아 return 하도록 해보자.

제한 사항

• 모든 공항은 3글자 알파벳 대문자로 이뤄짐.
• 공항의 수는 3개 이상 10000개 이하
• ticket의 각 행 (a,b)는 a에서 b 로 가는 항공이란 의미
• 주어진 항공권은 모두 사용해야 함
• 사용 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return함(sort 함수 사용)
• 모든 도시를 방문할 수 없는 경우는 없음

위의 문제 사항을 듣고 푼 문제

function solution(tickets) {
    let answer = [];
    tickets.sort();

    let findlist = new Map();
    let findset = new Set();

    tickets.forEach(element => {
        if(!findlist.has(element[0]))
        {
            let list = new Array();
            list.push(element[1]);
            findlist.set(element[0], list);
        }
        else
        {
            findlist.set(element[0], [...findlist.get(element[0]), element[1]]);
        }

        findset.add(element[0]);
        findset.add(element[1]);
    });

    for(let key in findlist)
    {
      findlist[key].sort();
    }

    findlist.get('ICN');
    answer.push('ICN');
    //키를 입력해서 findlist에서 탐색을 시작하자.
    function dfs(key)
    {
        if(findlist.has(key))
        {
            let checklist = findlist.get(key);
            checklist.forEach(element => {
                answer.push(element);
                dfs(element);
            });
        }
        else
        {
            if(findset.size > answer.length)
            {
                answer.pop();
                return;
            }
            
        }
    }

    return answer;
}

뭔가 풀이가 길어져 버린 것 같고 답이 맞는지 체크는 해보지 못했지만 일단 dfs 방식의 연습으론 괜찮았던 것 같다.