요즘시대에 여행경로 구하기 DFS

About this offer

소집해제도 다가오고 어떻게 될진 모르겠지만 알고리즘을 한번 풀어보자. 요즘 문제 푸는 재미가 꽤나 쏠쏠하다 그리고 Riv Animation을 잘만들어주는 스킬을 요즘 계속 다듬고있는데 점점 할수록 퀄리티가 올라가는게 보여서 재밌다. 다음에 시간이 되면 Rive 공식 커뮤니티에 기고해볼 예정이다. Skill을 비대하게 만들지 않는것이 중요하다 생각했는데, 의도치않은 결과물이 생기면 단순히 그 문제 케이스에 대해서만 지침을 추가해 구멍을 메꾸는게 아니라 AI가 어떤 점을 미처 생각하지 못해서 이런식의 결과물이 나올 수 있는지 먼저 얘기하는 시간을 가지니까 스킬을 만들면서 나까지 학습이 되는거 같다. 뭐 어쨌든 본격적으로 문제를 풀어보자 대략 한 40분 정도 소모된거같다. 문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/43164# 문제 설명 시작 지점 a 공항에서 b 공항으로 가는 항공권들인 tickets 를 받고 주어진 항공권을 모두 사용하여 여행 경로를 짜야하는 문제이다. 제약은 다음과 같다. 공항은 최소 3개 이상 10,000개 이하이다. 이때 항공권을 모두 사용한 가능한 여행 경로가 2개 이상이라면 알파벳 순서에 앞서는 경로를 return한다. 아이디어 방향이 있는 그래프 구조라고 생각했고 DFS를 이용해서 완전탐색을 하면 쉽게 풀릴 문제다. 순서도를 구해보자면 ICN에서 시작하면서 순회를 시작한다. 사용하지않은 티켓들중에 현재 startPoint로부터 갈 수 있는 티켓들을 getCanBeNextDestination 로 구한다 이를 candidates 라고 한다. candidates 만큼 for문을 돌면서 dfs 순회 시작한다. 그리고 남은 티켓에서 해당 candidate 티켓을 제거한다. candidates 가 더이상 없으면 종료하고 남은 티켓이 없다면 한번 다 순회했다는 의미이므로 가능한 경로를 의미하는 allTravelRoutes 에 해당 경로를 넣는다. 가능한 경로가 여러개일 경우 알파벳에 우선하는 경로를 return 해야하므로 sort를 이용해서 정렬 후 값을 return한다. 시간 복잡도 하나를 각각 선택하고 candidates의 개수에 따라 dfs 실행을 반복하기때문에 O(N!)이다 출발지와 도착지가 정해져있기때문에 무분별하게 탐색을 위한 분기하진 않지만 최악의 경우에는 O(N!)이다 문제 유형 완전탐색 문제다 문제를 다 풀고나서 시간 복잡도가 O(N!)이 나와버리니, GPT한테 다른방식으로 풀 수 있냐고 물어보니까 오일러 경로와 Hierholzer 알고리즘을 사용할 수 있다고 했는데 이건 다음 포스팅에서 알아보자. 전체 코드 function solution(tickets) { var answer = []; const allTravelRoutes = []; const getCanBeNextDestination = (startPoint, unusedTickets) => { const candidates = unusedTickets.filter(([startAirport, destination])=>{ return startAirport === startPoint }) return candidates; } const dfs = (originPort, travelRoutes, unusedTickets) => { if (unusedTickets.length === 0) { allTravelRoutes.push([...travelRoutes, originPort]); }else{ const candidates = getCanBeNextDestination(originPort,unusedTickets); if(candidates.length === 0) return; for(let i =0; i<candidates.length; i++){ const index = unusedTickets.findIndex(ticket => ticket[0] === candidates[i][0] && ticket[1] === candidates[i][1]); const newUnusedTickets = unusedTickets.filter((_, i) => i !== index); dfs(candidates[i][1], [...travelRoutes, originPort],newUnusedTickets ) } } } dfs("ICN",[],tickets) allTravelRoutes.sort((a,b)=>{ for(let i=0; i<a.length; i++){ if(a[i] < b[i]) return -1 if(a[i] > b[i]) return 1 } return 0; }) return (allTravelRoutes[0]) };

Offer details

Provider

velog

Source

velog-rss

Score

54.39

Confidence

49%