[Programmers] 여행경로

문제

 

깊이/너비 우선 탐색(DFS/BFS) > 여행경로

코딩테스트 연습 - 여행경로

 

 

아이디어

 

이번 문제의 아이디어는 DFS입니다.

 

기본적인 DFS문제라고 생각돼서 DFS이다! 말고는 추가적인 견해는 필요 없을 것으로 보입니다.

 

재귀 함수를 이용하여 최대 깊이까지 탐색한 후 가능한 경로가 여러 개일 경우는 알파벳 순서가 앞인 경로에 대해서만 결과로 보여주면 쉽게 풀 수 있을 것으로 보입니다.

 

 

구현 코드 (JavaScript)

 

const res = [];

const solve = (start, count, array, tickets, visited) => {
    if(count === tickets.length) { // DFS로 모든 티켓들을 순회했을 경우
        array[count] = start;
        
        if(res.length === 0) { // res에 초기적재하는 경우
            for(let i=0; i<array.length; i++) {
                res[i] = array[i];
            }
        } else {
            for(let i=0; i<array.length; i++) { // res와 array를 비교하기
                if(array[i] < res[i]) { // 알파벳 순서가 더 앞설경우
                    for(let j=0; j<array.length; j++) { // res에 array값을 저장
                        res[j] = array[j];
                    }
                    break;
                } else if(array[i] > res[i]) { // 알파벳 순서가 앞서지 못할 경우
                    break;
                }
            }
        }
        
        return;
    }
    
    for(let i=0; i<tickets.length; i++) {
        const ticket = tickets[i];
        if(!visited[i] && ticket[0] === start) { // 아직 공항티켓을 사용하지 않고 출발도시일 경우
            visited[i] = true;
            array[count] = start;
            solve(ticket[1], count+1, array, tickets, visited);
            visited[i] = false;
        }
    }
}

function solution(tickets) {
    
    const array = new Array(tickets.length+1); // DFS를 통해 공항티켓을 저장하는 배열
    const visited = new Array(tickets.length).fill(false); // 공항티켓 사용여부 확인
    
    solve("ICN", 0, array, tickets, visited); // (출발지점, 선택된 티켓개수, DFS를 통해 공항티켓을 저장하는 배열, 공항티켓들, 공항티켓 사용여부 확인)
    
    return res;
}

 

 

 

읽어주셔서 감사합니다.