🤪bfs 방문 체크를 언제 할 것인가에 대한 고찰.

bfs에서 방문체크를 언제 할것인가?

• 시행착오

  -큐에 넣는 순간에 방문변수를 true로 만들 것인가?
  -큐를 뽑는 순간 에 방문변수를 true로 만들 것인가?

🤪왜 그래야 하는건데? : 논리적 관점.(240116)

: bfs 라는 것이 동일한 가중치를 가지고, 인접한 정점들을 탐색하는 것임.
a 에서 b를 탐색시 가중치가 1인 경우에 이미 방문처리를 함.
체크를 해야지만, c에서 b로 올때 방문 못하게 차단 할 수 있음.
만약 방문 체크를 하지않는다면, a-> b -> c -> b로 오게 되는데
b로 향하는 가중치 누적값은 3에 해당함.
따라서 방문 기록 체크는 for문에서 큐 삽입시 반드시 해야 함!

결론

: 방문체크는 인접한 부분에서 큐에 삽입하는 순간에 방문 체킹을
해서 중복으로 들어오는 것을 방지하자!

아래는 이전 내용.. 그닥..

---

인구이동 문제를 통한 방문 변수 체킹 시점

• 1)올바른 시점
  

• 2)잘못된 시점
  

• 내가 여기다가 왜 했을까에 대한 고찰
  : 시작 포지션의 방문체크까지 한번에 진행하려고 여기다가 했음.

  차라리 큐 반복문 들어오기전에 체크하는 것이 가장 안정적인 형태임

• 결과
  : 입력예제 5번을 통해서 진행함.

• 1) 올바른 시점
  : 전부 다른 위치값이 기록됨.
  

• 2) 잘못된 시점
  
  : 2개의 중복된 값이 들어오는 것을 확인할 수 있음.

왜 이러냐면? 체크 조건을 true 설정하는 구간이 큐 팝하는 부분이기 때문에
팝 하기전에 인접한 부분을 중복해서 넣을 수 있음.