- Published on
프로그래머스 여행경로 (bfs/dfs)
- Authors
- Name
- Deokgoo Kim
문제 풀이
bfs/dfs 분류의 문제입니다.
난이도는 중간 이라고 생각합니다.
function solution(tickets) {
let answer = [];
let visited = [];
// 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.
// 따라서 sort를 진행하였습니다.
tickets = tickets.sort((a, b) => {
if (a[0] > b[0]) return 1;
if (a[0] < b[0]) return -1;
if (a[0] === b[0]) return a[1] > b[1] ? 1 : -1;
return 0;
});
// 출발지가 contry가되며 아직 방문하지 않은 곳을 찾습니다.
const getIndexFromStart = (contry) => {
const res = [];
tickets.forEach((x, idx) => {
if (x[0] === contry && !visited[idx]) res.push(idx);
});
return res;
};
const dfs = (contry, level) => {
const correctIndex = getIndexFromStart(contry);
if (!correctIndex.length) return;
while(correctIndex.length) {
if(answer.length === tickets.length + 1) return;
const idx = correctIndex.shift();
const target = tickets[idx][1];
answer[level] = target;
visited[idx] = 1;
dfs(target, level + 1);
visited[idx] = 0;
}
};
answer.push("ICN");
dfs("ICN", 1);
return answer;
}