bfs 문제에서의 visited에 처음 진입한 값은 반드시 최소인가? : 250921

• bfs는 동일한 가중치를 가지고 인접한 pos에 진입하게 된다.
  즉 가장 먼저 visited = false에 도달할때 , 그 pos까지의 dist는 그 pos에서의 최단거리이다.

• 반론적인 생각으로 돌아서 와서 도달하고, 종점으로 나아갈때가 최소가 될 수 있지 않을까? 라는 나의 상상을 하는데.

• 해당 pos에서 생각해보자. pos에서 destPos까지의 최단 경로가 이미 정해져있다고 하자. 여기서는 초록색 선인 3번이다.

• 그렇다는 것은 start점에서 target 으로 먼저 진입하는 순간이
  가장 최소의 값이다. 왜냐하면 모든 가중치가 동일하기 때문이다.

• 결론
  : bfs에서 visited 먼저 도달하는 상황이 최단거리이고, 반드시 visited 필요하다. 다음 순회하는 곳에서 다시 방문하는 경우도 차단해야 한다.

---

언제 bfs를 사용할까? 241029

: 동일한 가중치를 가지고 있을 때! bfs를 사용한다.

최단거리를 구할때는 이전좌표값을 받아와 사용하자.

• 게임맵 최단거리, 미로 탈출
• 비슷한 유형 : 2021 카카오 거리두기 확인하기

bfs 할때

1) 테두리 체크
2) 방문 체크
-> 무조건 한번만 방문 가능하므로, 다른 인접리스트 접근이 불가함

체크 변수 필요 없는 경우

• bfs로 접근할때 불변수를 이용해 사용유무를 확인하는데,
  그렇지 않은 경우도 있다.

• 예시 : 이코테의 미로탈출, 프로그래머스의 게임 맵 최단 거리가
  이에 해당한다.

• 카카오 경주로 건설도 포함.

• 어떻게 구별할 수 있냐면 컨테이너의 값을 통해서 접근할 수 있는 수와 접근할 수 없는
  수로 제한되어 있을 경우에 해당한다.

• 최단경로가 아니라 최단 비용을 구할때 불변수 필요 없다.

• 예시
  1 1 0
  0 1 0
  0 1 1
  (0,0)에서 (2,2)까지 가야할 경우가 속한다.

중요한 부분!

• 여기서 중요한 부분이 (0,0)에서 (0,1)로 이동한 후,
  (0,1)에서 (0,0)을 또 탐색할 수도 있다는 건데,
  1 2 0
  0 1 0
  0 1 1
  ->
  3 2 0
  0 3 0
  0 1 1
  ->
  3 2 0
  0 3 0
  0 4 1
  -> 최종 결과
  3 2 0
  0 3 0
  0 4 5

-> 이렇게 된다.
(0,1)에서 2가 5로 되지 않는 이유는
갈수 있는 값이 1이라는 조건이 있기 때문에 가능한 것이다.
그것을 염두에 두고 코드를 짜면 시작점을 어떻게 처리할 것인지에 대한
고민이 필요없다.