문제 설명
주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 "ICN" 공항에서 출발합니다.
항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요.
제한사항
모든 공항은 알파벳 대문자 3글자로 이루어집니다.
주어진 공항 수는 3개 이상 10,000개 이하입니다.
tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다.
주어진 항공권은 모두 사용해야 합니다.
만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.
모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.
입출력 예
| tickets | return |
|---|---|
| [["ICN", "JFK"], ["HND", "IAD"], ["JFK", "HND"]] | ["ICN", "JFK", "HND", "IAD"] |
| [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]] | ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] |
문제풀이
블로그를 참고해서 풀었습니다!
요 문제에서는 우린 경로를 출력해주어야 합니다. 따라서 DFS를 사용했습니다.
일단 저는 BFS는 최단거리에서 사용해야 하고 DFS는 경로의 특성을 이용해야 하는 경우에 사용해야 하는것이라구 일단..그렇게 이해했스빈다! 그리고 모든 노드를 방문해야하는 문제 같은 경우는 둘 다 사용해도 무관!
결과코드
function solution(tickets) {
let answer =[]; //정답
let result=[]; //경로를 표시해줄 아이
let visited=[]; //방문 노드
tickets.sort();
function dfs(node,cnt){
result.push(node); //현재 노드 값을 넣어줌
//카운트수랑 노드수가 동일한 경우 모든 노드를 방문했다는 의미이므로 끝!
if(cnt === tickets.length){
answer = result;
return true; //재귀이기 때문에
}
//현재노드를 찾기 위해서 반복문 이용
for(let i=0;i<tickets.length;i++){
//현재노드가 방문하지 않았을 경우
if(!visited[i] && tickets[i][0]===node){
visited[i]=true; //방문처리
if(dfs(tickets[i][1],cnt+1)) return true;
visited[i]=false; //만일 위 재귀에서 탐색에 실패했다면 방문하지 않았으므로 false로 변경해주기
}
}
//탐색에 실패한 경우처리
result.pop(); //결과 경로에서 삭제해주어야 하므로
return false; //위에 조건문에 false 값을 반환하기 위함
}
dfs("ICN",0);
return answer;
}재귀의 형태를 이해하는게 좀 어려웠던 문제였습니다. 그래서 냅다 걍 출력해서 확인해봤어요
if(dfs(tickets[i][1],cnt+1))
{
console.log(tickets[i][1]+","+(cnt+1));
return true
};조건문 부분에 저렇게 콘솔을 찍어줬더니
테스트1)
입력값)
[["ICN", "JFK"], ["HND", "IAD"], ["JFK", "HND"]]
출력)
IAD,3
HND,2
JFK,1
테스트2)
입력값)
[["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL", "SFO"]]
출력)
SFO,5
ATL,4
SFO,3
ICN,2
ATL,1
가 요렇게 찍혔습니다. 요말은 즉슨 재귀는 파고파고파고 들어간다!!! 요렇게 이해하면 될거같아요.
1번의 경우를 보면
첫번째 탐색
ICN -> JFK
두번째 탐색
JFK -> HND
세번째 탐색
HND -> IAD
마지막 탐색
IAD는 탐색 못합니다. 왜냐면 카운트수랑 노드수가 동일하거든용! 그말인 즉슨 탐색끝!
근데 출력은 지금 IAD 부터 되고있져? 그니까 탐색을 왈랄ㄹ랄랄라 하고 탐색 실패 부터 함수를 하나씩 빠져나오니까 출력은 저렇게 되는겁미다!!
암튼 요렇게 이해를 하시면..
아글고!! 이문제에서 탐색을 하지 못했을경우!!!
//탐색에 실패한 경우처리
result.pop(); //결과 경로에서 삭제해주어야 하므로
return false; //위에 조건문에 false 값을 반환하기 위함요 부분 처리를 꼭꼭꼭~!!!!!!!!!!!! 잊으면 안된다고 다른 사람들은 다들 알겠지만... 저는 모르니까 기억할게요!!^^ 헤헤
이만 물러갑니다...총총~
