문제 분석 241101

• 기존의 bfs 처럼 여기서 visit 처리하게 될 경우,
  완료 정점 k까지는 단 한번만 들어오게 된다.
  이것은 옳지 못하다.

-> 왜냐하면 for문에 진입하는 순간 동일한 가중치 3개의 가는 방법에서도 3개 모두가 k로 도달하는 경로가 있을 수 있다.
따라서 visit 처리를 다른 곳에서 해야 한다는 것을 번뜩여야 한다!

• 주의할 점
  : 10만 까지 포함해야 한다.....
  -> 문제를 잘 읽고 크기 할당하자...

---

240117 추가

• 방문 체크를 위한 불변수와 현재 노드번호와 비용을 가지고 있을 자료구조가 필요함.
  vector visited , queue<int node , int cost>
  

• 문제에서 최소 시간과 카운팅을 구하는 것이기 때문에
  : 카운팅을 할 수 있는 뭔가가 있어야 함.
  : bfs 이기 때문에 bool visited 필요함.

• 중요함
  : 만약에 vector visited 를 통해서 0이 아닌 경우만 체크를 한다고 하면 문제가 되는게 , 문제는 최소 시간에 도착할 수 있는 모든 경우의 수를 구하는 것이기 때문에
  vector visited 로 조건 처리하게 되면, 여러 경우의 경로를 구할 수 없음.
  -> 기존과는 다른 시퀀스로 방문처리를 해야함!

  • 따라서 반드시 visited 와 pair<nodeNum , cost> 2개로 나뉘어서 진행해야 함.

  • 아니면 cost[정점번호] 에 대한 카운팅을 통해서 visited[target] 이 최소 비용인지를 확인하는 방법으로 접근하자.

🍒핵심 240118 추가함.

: 방문처리를 어디서 할 것이냐에 대해서...

• 참고 사이트
  : https://hagisilecoding.tistory.com/104
• 기존의 방식대로 for문에서 visited 체크를 할 경우, 중복 타겟 정점으로의
  queue 삽입은 불가함.
  vector dir {-1,1,2}
  for(int i = 0 i < 3; ++i)
  {
  // 타겟정점 방문 안했을 때, true 하게 되면,
  // 만약에 여기서 동일한 정점을 동일한 가중치로도 접근이 가능할 수 있음!
  // 예를 들면 , 1에서 4로 간다고 하면
  // 1 -> 2(더하기 1번 인덱스 사용) -> 4
  // 1 -> 2(곱하기 2번 인덱스 사용) -> 4
  // 위의 2개 예시를 통해서 여기서 방문 처리하면 안됨.
  }
• 논리적인 접근.
  방문처리는 queue에서 pop할 때 방문처리를 하자.
  논리적으로 생각하면, 최단 시간에 진입하고, 동일한 비용이 나왔다고 하는 것은
  for 문 돌때 동일한 가중치로 갈수 있는 또 다른 방법이라는 것이기 때문에
  for 문에서 방문 처리하면 안된다는 것을 알 수 있음.