여행경로

Problem. 여행경로

---

Link.

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

프로그래머스

---

Description.

주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다.

항상 "ICN" 공항에서 출발합니다.

항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때,

방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성하세요.

 

※ 제한사항

• 모든 공항은 알파벳 대문자 3글자로 이루어짐
• 주어진 공항 수는 3개 이상 10,000개 이하
• tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미
• 주어진 항공권은 모두 사용해야함
• 만일 가능한 경로가 2개 이상일 경우, 알파벳 순서가 앞서는 경로를 return
• 모든 도시를 방문할 수 없는 경우는 주어지지 않음

입출력 예시

---

Approach. 

1) 배열 tickets 알파벳 순으로 정렬

• 문제 조건을 만족시키기위해 배열 tickets 알파벳 순으로 정렬

// 원본 배열을 복사 및 알파벳 순으로 정렬
let sortedTickets = tickets.sort();

 

2) DFS 함수 정의

• 배열 words 요소중 target이 없는 경우 0을 반환

 

Step#1. 현재 탐색 종료조건 (solution을 찾은 경우)

• solution을 이미 찾은 경우, 추가적인 경로 탐색은 하지 않는다 (∵ 알파벳 순서대로 정렬했기 때문)

// 최초 경로를 찾으면, 탐색종료
if(answer.length !== 0)
	return;

 

Step#2. 경로 탐색

• right (이전 배열의 오른쪽 요소)와 newLeft (현재 배열의 왼쪽 요소)가 일치할 경우, 원본 배열(list)를 복사한 배열(copyList)에서 현재 Index에 해당하는 요소 제거
  • 마지막 탐색인 경우, answer에 solution을 저장한 후 DFS 종료
  • 이외의 경우, 추가적으로 DFS 탐색

for(let i = 0; i < list.length; i++) {
	let newLeft = list[i][0];
            
    if(right === newLeft) {
    	let copyList = list.slice();
        let newRight = copyList[i][1];
        copyList.splice(i, 1);
                
        // 마지막 탐색인 경우
        // 배열 answer에 solution 저장후 탐색종료
        if(copyList.length === 0) {
        	answer = [...sAnswer, newLeft, newRight];
            break;
        }
        // 이외의 경우, 추가적으로 DFS 탐색
        else 
        	DFS(copyList, newRight, [...sAnswer, right]);
   }
}

 

Step#3. 결과 반환

return answer;

---

My Answer. 

function solution(tickets) {
    // solution을 담을 배열 answer 정의 
    let answer = [];
    
    let len = tickets.length;
    
    // 원본 배열을 복사 및 알파벳 순으로 정렬
    let sortedTickets = tickets.sort();
    
    // DFS 정의
    const DFS = (list, right, sAnswer) => {
        // 최초 경로를 찾으면, 탐색종료
        if(answer.length !== 0)
            return;
        
        for(let i = 0; i < list.length; i++) {
            let newLeft = list[i][0];
            
            if(right === newLeft) {
                let copyList = list.slice();
                let newRight = copyList[i][1];
                copyList.splice(i, 1);
                
                // 마지막 탐색인 경우
                // 배열 answer에 solution 저장후 탐색종료
                if(copyList.length === 0) {
                    answer = [...sAnswer, newLeft, newRight];
                    break;
                }
                // 이외의 경우, 추가적으로 DFS 탐색
                else 
                    DFS(copyList, newRight, [...sAnswer, right]);
            }
        }
        
        return;
    }
    
    for(let i = 0; i < sortedTickets.length; i++) {
        // 배열 i번째 배열의 왼쪽 요소
        let left = sortedTickets[i][0]
        // 정렬된 배열 복사
        let list = sortedTickets.slice();
        
        // 배열 왼쪽 요소가 ICN일 경우
        if(left === "ICN") {
            // 배열 i번째 배열의 오른쪽 요소
            let right = list[i][1];
            // 복사된 배열에서 고려한 요소 제거
            list.splice(i, 1);
            // 남은 배열로 DFS 탐색
            DFS(list, right, [left]);
        }
    }
    
    return answer;
}

---

References.

프로그래머스 - 코딩테스트 연습 힌트 모음집:

https://school.programmers.co.kr/learn/courses/14743/lessons/118891

프로그래머스

---

For Developer. 

• 잘못되거나 부족한 부분이 있다면 언제든지 댓글 부탁드립니다 :)