프로그래머스 [Lv. 3] 여행경로 {언어 : JavaScript}

문제 링크

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

프로그래머스

정답 코드

function solution(tickets) {
    let answer = [];
    let isFound = false;
    const lenTickets = tickets.length;
    const adjL = {}
    const visited = {}
    tickets.forEach(([s, e]) => {
        if (visited[[s, e]] == undefined) {
            visited[[s, e]] = 1;
        } else {
            visited[[s, e]] += 1;
        }
        if (adjL[s] == undefined) {
            adjL[s] = [e]
        } else {
            adjL[s].push(e)
        }
    })
    const node = Object.keys(adjL)
    
    node.forEach((k) => {
        adjL[k].sort();
    })
    
    const dfs = (l, current, res) => {
        if (isFound) {
            return
        }
        
        if (l == lenTickets) {
            answer = res;
            isFound = true
            return
        }
        if (adjL[current] == undefined) {
            return
        }
        for (const next of adjL[current]) {
            if (visited[[current, next]]) {
                visited[[current, next]] -= 1;
                dfs(l+1, next, [...res, next]);
                visited[[current, next]] += 1;
            }
        }
    }
    
    dfs(0, "ICN", ["ICN"])

    return answer;
}

풀이 방법

1. adjL과 visited 배열을 딕셔너리 형태로 만든다.
   1. 자바스크립트에서는 객체라고 부르는 것 같다.
   2. visited배열의 경우 혹시나 같은 항공권이 하나 이상일 수 있다고 가정했다.
2. node라는 변수명으로 공항만 따로 모았다.
3. 정렬을 미리 해준다.
   1. 정렬을 미리 해주면 나중에 결과값을 모아서 따로 정렬할 필요가 없어진다.
4. dfs를 실행한다.
   1. isFound가 false이면 아직 답을 찾지 못했다.
   2. 티켓을 모두 소진했을 경우 바로 answer값에 res를 넣고 isFound를 true로 바꾼다.
   3. 현재 지점에서 다음 지점으로 가는 티켓이 없는 경우 undefined이다.
      1. undefined인 경우 당연히 종료
   4. 다음으로 가는 티켓이 있는 경우 visited배열을 확인한다.
      1. 배열의 값이 1이상인 경우 1을 뺀다.
      2. dfs를 실행하는데 깊이를 늘려주고, 다음 지점을 결과 값에 넣는다.
      3. return으로 돌아온 경우 다시 1을 더해준다.
5. answer를 출력한다.

느낀점

• 출발 지점이 무조건 ICN인걸 몰랐다.
• 문제를 처음부터 끝까지 다 읽는 습관을 들이자.