💻 BFS/DFS by 프로그래머스 연습문제

다음주에 바닐라JS를 학습하는데 나는 바닐라JS로 무언가를 만들어 본 적이 없기 때문에 시간이 오래 걸릴 것 같아서 미리 강의를 들었다.
그래서 다음주에 학습할 BFS/DFS 에 대해서 미리 다뤄보려고 한다.

📍 BFS / DFS

너비 우선 탐색(BFS)

• 그래프 탐색 알고리즘으로 같은 깊이에 해당하는 정점부터 탐색하는 알고리즘
• 큐를 이용하여 구현
• 시작 지점부터 가까운 정점부터 탐색

깊이 우선 탐색(DFS)

• 그래프 탐색 알고리즘으로 최대한 깊은 정점부터 탐색하는 알고리즘
• stack을 이용하여 구현
• 시작 정점에서 깊은 곳부터 탐색

여행경로

출처 : 프로그래머스
여행 경로

내 답안

function solution(tickets) {
  const airportMap = new Map();
  for (const [start, dest] of tickets) {
    if (!airportMap.has(start)) {
      airportMap.set(start, [dest]);
    } else {
      airportMap.get(start).push(dest);
    }
  }

  for (const [start, dest] of airportMap.entries()) {
    dest.sort().reverse();
  }

  const travelRoutes = [];
  const stack = ["ICN"];
  while (stack.length) {
    const city = stack[stack.length - 1];

    if (!airportMap.has(city) || airportMap.get(city).length === 0) {
      travelRoutes.push(stack.pop());
    } else {
      stack.push(airportMap.get(city).pop());
    }
  }
  return travelRoutes.reverse();
}

💡구현 방법

1. airportMap를 Map으로 선언하여 key에는 출발하는 공항을, value 는 도착하는 공항들을 초기화시켜준다.
2. 경로가 2개 이상일 경우 알파벳 순으로 정렬해야하기 때문에 목적지를 정렬해준다.
3. stack으로 DFS를 구현하였는데 우선 "ICN"부터 추가해 놓는다.
4. airportMap에 도시(공항)이 없거나 도시로부터 갈 수 있는 공항이 없을 경우에는 travelRoutes(여행경로)에 추가해 주고 아닐 때에는 스택에 다음 갈 공항을 추가해주면 된다.

🔥 느낀점(오늘의 회고)

오늘은 하루종일 대부분 과제에 매진하였다. 트리의 순회를 직접 구현, 그리고 트라이를 이용하여 자동완성 코드를 구현하는 것이었다. 아직 PR을 올리지는 않았지만 스스로 구현했다는 것에 칭찬해주고 싶다. 물론 구현 못한 부분(스택으로 구현한 후위 순회)도 있다..😂 이 부분은 나중에 따로 정리해둬야지

그리고 다음주부터 바닐라JS를 시작한다. 한번도 이것으로 무언가를 만들어 본적이 없어서 걱정된다. 미리 한 번 보고 왔지만 따라가기 조금 벅차지 않을까 싶다. 뭐 어쩌겠어~ 시간을 더 투자해야지! 그러니 미리미리 강의를 들어두자

새롭게 느낀 것도 있는데 체력관리를 잘 해야 겠다는 것이다.💪🏻💪🏻 계속 컴퓨터 앞에 앉아있고 운동도 거의 안하기 때문에 몸의 컨디션이 안좋아지는게 조금 느껴진다.😩
이래서 운동이 중요한건가..😭 PT를 끊어야할까..? 고민해보자!
또한 피곤해도 새벽 2시-3시 안에는 자도록 노력해야겠다!

Refer

코딩테스트 연습 | 프로그래머스

오늘의 내용 정리

데브코스 주말