언제 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이라는 조건이 있기 때문에 가능한 것이다.
그것을 염두에 두고 코드를 짜면 시작점을 어떻게 처리할 것인지에 대한
고민이 필요없다.