등산코스 정하기

문제 설명

산에 n개의 지점이 존재하며, 지점들은 아래와 같이 정의된다.

• 출입구
• 쉼터
• 산봉우리

각각의 지점들은 그래프로 주어진다.

등산코스를 정할 때, 산봉우리 중 한곳만 한번만 방문하고 다시 출입구로 돌아와야한다. 등산코스를 따라 이동하는 중 쉼터 혹은 산봉우리를 방문할 때마다 휴식을 취할 수 있으며, 휴식 없이 이동해야 하는 시간 중 가장 긴 시간을 해당 등산코스의 intensity라 한다.

처음 출발한 출입구로 다시 되돌아 가야 한다.

최소 intensity가 되는 등산코스를 찾아라!

즉, 특정 산봉우리와 해당 산봉우리로 경로를 지정 했을 때, 최대크기 간선이 최소가 되어야 한다.

문제 접근 방식

가본 관점

• 봉우리 찍으면 더 이상 bfs를 진행하지 않아도 된다
• 최대 크기 간선이 최소가 되는 경로를 선택한다
• 간선크기가 글로벌 최소 간선 크기를 초과하면 백 트래킹 한다
• 모든 산봉우리를 확인해봐야한다

추가 관점

• intensity가 최소가 되는 등산코스가 여러 개라면 그중 산봉우리의 번호가 가장 낮은 등산코스를 선택
• 노드가 gates나 summits의 원소인지 판단할 때 선형 검색을 하면 최악의 경우에 O(n)이 걸린다

  gates, summits를 dictionary로 변환 후 사용

• visited를 리스트로 작성하면 방문노드 확인할 떄, 최악 O(n)이 걸려버린다

  visited를 set으로 변환 후 사용 list find는 최악 O(n)인 반면 set find는 O(1)

• 큐에서 꺼낼 때, 짧은것부터 꺼내야댐

설계

1. bfs로 접근해보자(백 트래킹으로 최소 intensity를 초과할 때 컷할 수 있기때문에 선택)
2. 인접행렬그래프 생성X 2 <= n <= 50000이라서 그래프로 그리면 5만*5만이 되버린다. -> dictionary key 양방향으로 대체
3. bfs 설계
   1. 큐 : [ 현재 지점, 현재까지 최대 크기 간선, 방문한 지점 리스트 ]

      edge = defaultdict(list)
      for v1, v2, intensity in paths:
       edge[v1].append((v2, intensity))
       edge[v2].append((v1, intensity))
      

      느낀점

      visited 설계할 떄, list가 아닌 set을 씀으로써 속도가 더 빨라졌다. 큐에 set을 추가할 떄, visited.add()해서 visited를 그대로 넣어줬었다. 이 때, 주소값이 넘어가는 것이 아닌, 실제 value들만 넘어가기때문에 수월했다.

아니네…. 주소값이 넘어간다. 그래서 copy로 값만 가져와야됨.