문제 출처
나의 풀이
1차시도 (50/100)
ing 배열을 임의로 while 문 안에서 생성했으나, 로직이 맞지가 않는다. for문을 돌아서 ing 배열을 완성한 뒤 q에 값을 넣어주려 했으나, ing가 비어있는데 q.length는 여전히 남아 있는 경우가 계속 발생해서 런타임 에러가 발생한다.
사실 bfs로 구현하려고 시작했으나 결국 시작과 끝으로 이어지는 단일 꼬리물기가 되다보니 bfs보다는 dfs가 적합한 것 같다.
function solution(tickets) {
// 무조건 배열의 첫번째 원소가 아니라 "ICN" 공항부터!
let q = ["ICN"];
let ch = new Array(tickets.length).fill(0)
let visited = ["ICN"];
while (q.length) {
const start = q.shift()
let ing = []
for(let i=0; i<tickets.length; i++){
const [a, b] = tickets[i]
if(start === a && ch[i] === 0){
ing.push([b, i])
}
}
if(ing.length === 0) break
ing.sort((a,b) => a[0].localeCompare(b[0]))
q.push(ing[0][0])
visited.push(ing[0][0])
ch[ing[0][1]]=1
}
return visited
}
console.log(
solution([
["ICN", "SFO"],
["ICN", "ATL"],
["SFO", "ATL"],
["ATL", "ICN"],
["ATL", "SFO"],
])
); // ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"]
// console.log(
// solution([
// ["ICN", "JFK"],
// ["HND", "IAD"],
// ["JFK", "HND"],
// ])
// ); // ["ICN", "JFK", "HND", "IAD"]다른 풀이
tickets의 index와 동일한 visited 배열을 생성하고, 이 배열로 해당 경로를 사용했는지 아닌지를 추적한다.
공항을 오름차순해야 하는데,
출발 공항만 오름차순하는 게 아니라 도착 공항도 오름차순해야 한다. js에서 sort()는 문자열을 오름차순 정렬해주는 게 기본값이므로 이를 사용한다.
문제에서 요구하는 건 모든 항공권을 사용해서 도시들을 방문해야 한다는 점이다.
이는 모든 tickets의 배열을 사용할 수 있어야 한다는 의미이다.
tickets으로 가지를 뻗어나가며 가능한 경우의 수를 탐색하면 된다.
추적은 result 배열로 하는데
재귀가 시작되면 도시를 하나 삽입해놓고 가지를 뻗어나가면 count+1 하지만 가지를 뻗어나가다가 실패하면 다시 count-1도 하고 result 배열에서도 pop()하며 가능한 가지를 계속 뻗어 나간다.
이 과정을 반복하다가 요구하는 레벨까지 왔을 때 answer에 답을 넣어놓고 종료한다.
function solution(tickets) {
let answer = []
const visited = []
const result = []
const len = tickets.length
tickets.sort();
// console.log(tickets)
const dfs = (str, count) => {
result.push(str)
if(count === len) {
answer = result
return true
}
for(let i = 0; i < len; i++) {
if(!visited[i] && tickets[i][0] === str) {
visited[i] = true
if(dfs(tickets[i][1], count+1)) return true
visited[i] = false
}
}
result.pop()
return false
}
dfs("ICN", 0)
return answer
}다른 풀이 2
function solution(tickets) {
var answer = [];
DFS(tickets,'ICN',["ICN"]);
// console.log(answer.sort());
return answer.sort()[0];
function DFS(t,start,str){
// console.log("DFS t,start,str : ["+t+"],["+start+"],["+str+"]")
if(t.length == 0){
// console.log(str+"\n");
answer.push(str)
}
for(var i in t){
if(t[i][0] == start){
let tmp = t.slice();
tmp.splice(i,1);
let tmp2 = str.slice();
tmp2.push(t[i][1]);
DFS(tmp,t[i][1],tmp2)
}
}
}
}다른 풀이 3
이 문제에서 bfs는 시간이 오래 걸린다.
function solution(tickets) {
let answer = [];
let correctCount = tickets.length;
let withICN = [];
let withoutICN = [];
for (let i = 0; i < tickets.length; i++) {
if (tickets[i][0] === "ICN") withICN.push(tickets[i]);
else withoutICN.push(tickets[i]);
}
// 항상 ICN으로 시작하기 때문에 ICN을 기준으로 tickets을 정렬함
tickets = [...withICN.sort(), ...withoutICN.sort()];
function bfs(i) {
let visited = [];
let queue = [];
queue.push([tickets[i][1], [tickets[i][0]]]);
visited.push([i]);
while (queue.length) {
let current = queue.shift();
let checkVisited = visited.shift();
// 현재 저장된 값이 tickets의 길이와 같을 때
// 모든 여행경로를 돌고 마지막 공항에 도착한 경우
if (current[1].length === correctCount) {
// 해당 경우가 존재하면 값을 반환함
return (answer = [...current[1], current[0]]);
}
tickets.forEach((ticket, index) => {
if (checkVisited.includes(index)) return;
if (ticket[0] === current[0]) {
queue.push([ticket[1], [...current[1], ticket[0]]]);
visited.push([...checkVisited, index]);
}
});
}
}
// BFS를 활용하여 모든 경우의 수를 탐색함
for (let i = 0; i < tickets.length; i++) {
if (answer.length) {
return answer;
}
bfs(i);
}
}참고
https://medium.com/@wooleejaan