시작하며 🌈

시작한지 12시간만에 풀었네요. ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ
사실 BFS 아이디어는 바로 떠올랐는데, 최근에 재귀를 쓴 적이 거의 없어서, DFS로 도전했습니다. 결과는 매운맛이었어요. 🔥🔥🔥

제가 원래 한 고집하는 편이라, 어떻게든 풀 수 있을 때까지 잡아서,
결국에는 뭔가 일정들이 꼬이긴 했어요.

그래도 중요한 건, 제가 여태까지 풀이했던 과정들은, 분명 제 능력치가 될 거 같아요.

실제로, 정말 많은 것을 깨닫았어요! 설마 했던 부분에서, 자바스크립트 특성상 오류가 난 거더라구요. 그 오류만 7시간 동안 헤맸으니, 더 많이 새길 수 있었죠. (이는 풀이과정에서, 더 풀어볼까요 😋)

그래서 오늘은, 이에 관해서 포스팅을 해봐야겠어요. 그럼 시작할까요?!

풀이과정

저는, 다음과 같이 생각했답니다.

1. 일단 둘 다 풀 수 있을 거 같은데, DFS로 풀어보자.
2. 먼저 티켓의 시작, 도착 데이터에 따라 그래프를 하나 만든다. (사실 이거도 내 고집이다. 그냥 배열로 풀어도 무난하다.)
3. "ICN"으로 시작점을 설정한다.
4. 백트래킹을 한다. 만약 res가 티켓 수보다 길어지면 리턴해버린다.
5. 만약 같으면 가능한 전체 경로 케이스 배열인 allCases에 추가한다. (여기서 주의할 건, 제 설계의 경우 이게 최적의 경로가 아닐 수 있기 때문에 가능한 경우의 수를 다 뽑는 거에요! 참고로 이렇게 풀지 않아도 될 수도 있습니다.)
6. 현재 시작점에 해당하는 key값의 배열을 탐색한다. 하나 뽑아서 dfs를 호출한다. (재귀)
7. 완전탐색이 다 끝났으면 결국 케이스들이 모였다.
8. 정렬로 하나 뽑으면 끝!

인데...
제가 계속 놓쳤던 부분은요, deepCopy 였습니다.
제 기억에 다른 언어에서 비슷하게 해도 copy가 얕게 되지 않았던 부분이,
여기서는 얕게 복사돼서, 재귀를 썼을 때 계속 값이 얕은 복사가 되더라구요!

그래서 그때 잊었던 기억이 생각났습니다. 자바스크립트에서는 전체 객체가 객체타입이라 원시타입처럼 값만 복사를 하는 게 아닌, 주소값을 참조한다는 걸요!

따라서 결국 이를 디스트럭쳐링을 통해 해결했습니다. (이번에 해결하다 발견한 깊은 복사 꿀팁!)
12시간만에 풀었으나 아직도 꼬진 제 부끄러운 코드... 보고 도움이 되시길 바랍니다!

코드 💻

const makeGraph = tickets => {
    const graph = {}
    tickets.forEach(([from, to]) => {
        graph[from] = (graph[from] === undefined) ? [to] : [ ...graph[from], to ]
    })
    return graph;
};
const dfs = (start, ticketCounts, graph, nowCase, allCases) => {
    if (nowCase.length > ticketCounts) return;
    nowCase.push(start);
    if (nowCase.length === ticketCounts + 1) allCases.push([ ...nowCase ])
    if (graph[start] !== undefined) {
        graph[start].forEach((now, idx) => {
            const graphStart = [ ...graph[start] ]
            graphStart.splice(idx, 1);
            const copiedGraph = { ... graph, [start]: graphStart }
            dfs(now, ticketCounts, copiedGraph, [ ...nowCase ], allCases);
        })
    }
    return allCases
}

const solution = (tickets) => {
    const nowCase = [];
    const allCases = [];
    const graph = makeGraph(tickets);
    dfs("ICN", tickets.length, graph, nowCase, allCases);
    const selectedOptimizedCase = allCases.sort()
    return selectedOptimizedCase[0];
}

마치며 🎉

결국에는 고집으로 인해 많은 시간이 소요됐지만,
이 문제가 크던, 작던 간에 문제를 해결해냈어요.
남들에게는 단순한 코드여도, 저 자신이 자랑스러워요. 이상!!!