오랜만에 블로그글을 작성하는 거 같다.. 변명아닌 변명을 하자면 SSAFY에 지원하며 에세이작성, 시험 준비를 하느라... 결과는 다음주에 나오지만 흠.. 그 결과에 상관하지 않고 계속해서 준비를 해나가야겠다. 근데 참.. 그게 어렵다. 결과를 기다리면서 또 다시 준비해나간다는 게 내 부족한 점인 거 같다. 그럼에도 계속 나아가야지! 이번 기회에 나의 나약함(?)을 개선해보자 🔥
사실 DFS 공부를 하지 않고 있던 건 아니다. 정확히는 재귀함수를 사용하는 능력을 계속 길러왔다. 그 시간이 전보다 짧아졌을 뿐이다. 내가 해결했던 문제는 바로바로 "여행경로"문제이다.
여행경로
이 문제는 [인천,프랑스][프랑스 제주] [영국 미국][제주 영국]
위와 같은 출발지와 도착지 정보를 담고있는 이중 배열을 활용하여 가장 빠른 루트를 찾아 배열로 리턴하는 문제이다. 가장 빠른 루트라함은 최소한의 경유를 통해 도착지에 도착하는 경우이다. 무조건 서로 연결되어있고 ICN에서 출발하는 비행기가 첫 번째 경유지가 되어야한다. 그렇다면 어떻게 이 문제를 해결할 수 있을까?
[[ICN,JFK],[HND,IAD],[JFK,HND]] 의 여행경로가 있다면 ICN JFK HND IAD로 거쳐 들어가면 된다. 그렇다면 처음 로직은 이렇게 구성하였다.
- ICN이 담긴 배열의 [1]인덱스를 target으로 삼자
- target과 같은 [0]인덱스를 찾자
- 같고 방문하지 않았다면 target은 [0]인덱스가 되고 방문 기록을 해주자
- sum으로 경로를 저장하고 count를 높여 count가 tickets의 length와 같다면 answer arr에 push해주자.
- 그 중 가장 오름차순으로 배열하여 첫번째 인덱스를 return하자.
그림이 허접하지만 ..ㅋㅋ 다음처럼 로직이 돌아갔으면 좋겠다고 생각했다.
그렇다면 반복문이 재귀 안에서 한 번 밖에서 한 번 필요하겠다!
재귀 안에서의 반복문은 target과 같은 경유지를 찾기위해서
재귀 밖에서의 반복문은 재귀함수 실행 및 ICN을 시작점으로하는 index를 기준으로 경우를 따져줘야하기 때문이다.
코드를 먼저 살펴보면 다음과 같다.
여행경로
let tickets = [
["ICN", "SFO"],
["ICN", "ATL"],
["SFO", "ATL"],
["ATL", "ICN"],
["ATL", "SFO"],
];
function solution(tickets) {
let answer = [];
const ICNIndexArr = tickets
.map((item, index) => (item[0] === "ICN" ? index : null))
.filter((item) => item !== null);
//ICN이있는인덱스를찾음
let visited = Array.from({ length: tickets.length }, () => false);
// 방문확인을위해 배열생성
let target;
const dfs = (firstPort, sum, count) => {
if (count === 0) {
target = firstPort;
}
if (count === tickets.length - 1 && !answer.includes(sum)) {
sum = "ICN" + ` ` + firstPort + ` ` + sum.slice(0, -1);
answer.push(sum);
return;
}
for (let i = 0; i < tickets.length; i++) {
if (visited[i] === false && target === tickets[i][0]) {
visited[i] = true;
target = tickets[i][1];
sum = sum + target + ` `;
count = count + 1;
console.log(sum);
dfs(firstPort, sum, count);
target = tickets[i][0];
}
}
};
for (let i = 0; i < ICNIndexArr.length; i++) {
visited[ICNIndexArr[i]] = true;
dfs(tickets[ICNIndexArr[i]][1], ``, 0);
visited = Array.from({ length: tickets.length }, () => false);
}
answer = answer
.sort((a, b) => (a > b ? 1 : -1))
.map((item) => item.split(` `));
return answer[0];
}
solution(tickets);
하나하나 뜯어서 코드를 분석해보겠다.
let answer = [];
const ICNIndexArr = tickets
.map((item, index) => (item[0] === "ICN" ? index : null))
.filter((item) => item !== null);
//ICN를 출발지로 하는 배열을 filter하여 그 index를 찾아낸다.
let visited = Array.from({ length: tickets.length }, () => false);
// 방문확인을위해 배열생성
// 재귀함수 반복문 내부에서 방문했던 것은 방문하지 않기위해 visited 배열을 생성한다.
let target;
// 현재 위치를 저장하기 위해 target이라는 변수를 선언한다.재귀함수 내부의 for문
for (let i = 0; i < tickets.length; i++) {
if (visited[i] === false && target === tickets[i][0])
//방문하지 않은 경유지이고 target(현재위치)와 ticket[i]가 같다면?
{
visited[i] = true;
//방문처리를해주고
target = tickets[i][1];
//현재위치를 해당 출발지의 도착지로 옮겨주고
sum = sum + target + ` `;
//sum을 통해 저장 ` ` 를 더해준 이유는 ?? => 후에 배열로 변환하기 위해 split(` `)하기 위해서
count = count + 1;
//count를 높이는 이유는 ? => count를 높여 count와 ticket의 길이가 같아질 때 answer에 저장하기위해
dfs(firstPort, sum, count);
// 재귀함수 실행 후
target = tickets[i][0];
// 탈출하면 반복문이 돌아가기 이전의 현재위치로 돌아가 다른 경우의 수도 확인
}
}재귀함수의 종료조건
if (count === 0) {
target = firstPort;
}
//count가 0이면 target은 firstPort가 된다. 여기서 firstPort는 ICN으로 출발했을 때의 도착지가 된다.
if (count === tickets.length - 1 && !answer.includes(sum))
// 만약 count가 tickets.length-1과 같고 answer에 sum과 같은 string이 없다면 ?? answer에 추가
// string으로 저장한 두 번째 이유 => includes를 사용하기위해
{
sum = "ICN" + ` ` + firstPort + ` ` + sum.slice(0, -1);
//이때 sum을 재할당해서 answer에 넣기좋은 (원하는 result)로 만들기 좋은 형태로 만들어줌
answer.push(sum);
// answer에 push
return;
}재귀함수 외부의 for반복문
for (let i = 0; i < ICNIndexArr.length; i++) {
//ICN인덱스배열을 돌아야함으로 ICNIndexArr.length만큼돌기
visited[ICNIndexArr[i]] = true;
// 처음 ICN를 출발지로 하는 index는 true처리
dfs(tickets[ICNIndexArr[i]][1], ``, 0);
// 한번의 경우를 만들었다면 ? visited=새롭게 만들어줘야겠죠
visited = Array.from({ length: tickets.length }, () => false);
}
answer = answer
.sort((a, b) => (a > b ? 1 : -1))
.map((item) => item.split(` `));
// answer을 오름차순으로만든 후 배열로 변환 후 [0]번 인덱스 return
return answer[0];
}이렇게 코드를 작성한 뒤 제출하면 ???
1번의 테스트케이스는 무엇일까?...
그렇기만 처음 풀어본 Level3문제였는데 해결해서 기분이 좋다..ㅎㅎ
다시 테스트 케이스 1번을 찾아 헤매보아야겠다.
사실 SSAFY 에세이를 작성한 후 한 5일정도 쉰 거 같다. 잠시 코드를 잘 안보고있으니 불안감도 커지고 자괴감도 온다.. 다시 또 달려보면 그런 잡생각이 날아가겠지..! 정신차리고 다시 달려보자. 화이팅 🔥
