반응형
BFS 방문 처리
- BFS의 방문 처리는 방문을 한 곳을 체크하는 것이 아니라 방문할 예정인 곳을 체크하는 방식이다.
- BFS를 풀 때 Queue를 보통 사용하게 되는데, 방문 체크를 Queue에서 데이터를 뽑을 때 방문 체크를 하는 것이 아닌, Queue에 집어넣을 때 방문체크를 하게 된다.
- 방문 한 곳을 체크한 경우, 방문 하진 않았지만 방문할 예정인 곳을 다른 곳에서도 접근 가능할 때 반복해서 탐색하는 경우가 생길 수 있다.
- 하지만 방문할 예정일 때 이를 체크한다면 이런 경우를 없앨 수 있다.
- 따라서 방문 한 곳 을 체크한다는 말은 틀린 말이고 방문 할 곳 을 체크하는 것이 적절한 말이다.
예제
728x90
'공부 > 알고리즘' 카테고리의 다른 글
[알고리즘/브루트포스/JAVA] 백준 1107 - 리모컨 (1) | 2023.03.06 |
---|---|
[알고리즘/DP/JAVA] 백준 2193 - 이친수 (0) | 2022.07.24 |
[알고리즘/재귀호출/Python] 백준 2747 - 피보나치 수 (0) | 2022.03.16 |
[알고리즘/계수정렬/Python] 백준 10989 - 수 정렬하기 3 (0) | 2022.03.16 |
[알고리즘/Union-Find/Python] 백준 4195 - 친구 네트워크 (0) | 2022.03.12 |