코테 스터디 32일차 TIL + 오늘의 학습 키워드 BFS

- 오늘의 학습 키워드
- 공부한 내용 본인의 언어로 정리하기

BFS 너비 우선 탐색을 활용

모든 0인 셀들을 시작점으로하여 동시에 BFS를 수행

각 0 에서 출발하여 인접한 셀들로 거리를 전파

이미 방문한 셀은 더 가까운 거리가 이미 계산 되었으므로 건너뜀

 

수도코드

결과 배열을 무한대로 초기화
큐 생성
모든 셀을 순회하면서:
  -0인 셀 -> 거리 0으로 설정, 큐에 추가

BFS 수행:
  -큐가 빌 때 까지:
    -현재 위치 poll
    -4방향 인접 셀 확인
    -더 짧은거리로 갱신 가능하면:
      거리 갱신
      큐에 추가

- 오늘의 회고
  - 어떤 문제가 있었고, 나는 어떤 시도를 했는지

DFS 인줄 알았는데 BFS가 더 효율적이라고함
  - 어떻게 해결했는지

BFS는 레벨별로 탐색하므로 처음 도달한 거리가 최단거리이다.

DFS는 모든 경로를 고려해야하므로 비효율적, 재귀 스택이 길어줄수 있
  - 무엇을 새롭게 알았는지

BFS 큐에 현재 레벨의 노드들만 저장할 수 있따.

DFS:  재귀 스택이 길어질수 있다.

poll의 역할

큐에서 제거하여 중복 처리를 방지한다. 지금 처리할 위치를 가져오고 큐에서 제거하는 역

BFS 레벨 진행

거리 0인 위치들-> 거리 1인 위치들-> 거리 2인 위치
  - 내일 학습할 것은 무엇인지