programmers_등산 코스 정하기_javascript

0. 생각의 흐름

1. paths를 돌면서 연결된 것들을 찾기
2. connect = [[1번과 연결되어 있는 지점들],[2번과 연결된 지점들],...];
   -> tree로 만들면 좋을듯?
   -> 아니다 산봉우리를 root로 두려 했는데, 산봉우리가 여러개일 수 있구나.
   -> dfs? 아냐 일단 재귀로 풀어보자. => 왜 이런 선택을 한거지?! 일단 그때 재귀가 끌린듯,,
3. gates를 돌면서 체크
   {
   - connect[gates - 1]부터 타고들어가며 시간 체크
   - 산봉우리를 만난 경우 다른 산봉우리들은 지나치도록 하며, 시작한 gate로 다시 올라가는 방법 탐색
   - 시작한 gate를 만나면 answer에 값을 저장했다가, 다른 값이 나오면 값을 비교하여 더 작은 값을 다시 저장.
   - answer에 있는 산봉우리와 다른 산봉우리일 경우, 해당 값이 같거나 작을때까지 변동 없음.
   - 만일 값이 같으면 더 작은 숫자의 산봉우리의 내용을 저장.
   - 값이 작으면 해당 산봉우리 내용으로 저장.
   }

1. 재귀로 푼 결과

이때는 꽤 하잖아? 하면서 뿌듯함이 가득했지만

곧....

안대...!!!!!

안되겠다, 다른 방법을 찾아보자
2022 테크 여름인턴십 코딩테스트 해설
팁을 참고!!

2. 놓치고 있던 부분

다익스트라 알고리즘

• 다익스트라 알고리즘이란? : 다이나믹 프로그래밍을 이용한 최단 경로 찾기 알고리즘.
  • 하나의 정점에서 다른 모든 장점으로 가는 최단 경로를 알려줌.
  • 하나의 최단 거리를 구할 때 이전까지 구했던 최단 거리 정보를 그대로 사용하며 효율을 높임.
    a. 하나의 정점 선택
    b. 해당 정점 이웃한 정점들의 비용을 각각 확인
    c. 그 중 가장 비용이 적은 정점을 기준으로 다시 한번 확인
    d. 이를 반복하며 최단 경로를 계속 갱신.

단방향

• 왕복을 생각하지 않고, 왔던 방향의 최소값이 돌아올때의 최소값이기 때문에 한 방향만 생각해 주면 됨!!
• 출입구에 연결된 양방향 등산로
  • 출입구에서 다른 지점으로만 이동 가능한 단방향 등산로
• 산봉우리 연결된 양방향 등산로
  • 다른 지점에서 산봉우리로만 이동 가능한 단방향 등산로

단방향을 알게되니 막상 현재 코드에 단방향을 넣어보고 싶게 됨..!!
혹시나 시간이 줄어들지 않을까? 싶은 마음에 단방향만 적용하여 다시 도전~!!

3. 재귀 + 단방향 결과

똑같이 시간초과 ㅠㅠ

4. 다익스트라로 푼 결과

추후 작성 예정