방문 체크하는 거 알겠고 cost 저장하는 거 알겠다.
근데 풀리지 않는 한 가지 의문.
왜 최초 방문된 행렬(위치)의 값의 cost 를 저장하는가...?
한 번 방문을 하고 나면 중복을 막기 위해 visited를 true로 처리하기 때문에
그 곳엔 다시 방문할 일이 없다. 그럼 그 곳의 cost는 한 번 저장되면 다신 바뀔 일이 없다는 얘기
..
....
.......
...........?
아니 어떻게 걔가 최소값인지 확신을 하고?
다른 최솟값의 길이 또 있을 지 어떻게 알고 cost를 막 저장해버리는 거지?
그래서 열심히 구글링 했다.
그러다 발견한 블로그 글
- 최단 경로 찾기: 그래프에서 두 지점 사이의 최단 경로를 찾아야 할 때 BFS가 유용하다.
- BFS는 너비 우선 탐색이므로 최단 경로를 찾는 데 효율적입니다.
- 최소 비용 문제: 경로의 가중치가 주어진 경우에는 BFS가 최소 비용 경로를 찾는 데 효과적이다.
- 모든 경로를 탐색하지 않고 먼저 발견된 경로가 최단 경로임을 보장합니다.
- 최단 경로가 유일한 경우: 최단 경로가 유일한 경우 BFS가 가장 효율적이다.
- 이 경우 BFS는 최단 경로를 찾는 데 시간복잡도가 더 낮습니다.
- 상태 공간 탐색: 상태 공간에서 최소 이동/변경 횟수를 찾는 문제에는 BFS가 적합하다.
- ex. 8 퍼즐, 스도쿠 등의 문제
!!!!!!!
모든 경로를 탐색하지 않고 먼저 발견된 경로가 최단 경로임을 보장합니다.
그렇다... BFS는 먼저 발견된 경로가 무조건적으로 최단 경로이기 때문에 묻지도 따지지도 않고 cost 값을 저장할 수 있는 거였음
DFS : 성공이던 실패던 끝까지 한 경로만 조짐 / BFS : 여러 경로를 한 단계씩 검색 -> 당연하게도 짧은 경로가 가장 먼저 도달함
지금 생각해보면 너비 우선 탐색이라는 어원부터 따져보면 너무나도 당연한 얘기였다....
그래서 최단 경로를 찾을 때 BFS 알고리즘을 쓰는 거고...
쓰다보니 1+1=2 이다를 장황하게 쓴 것 같긴하지만ㅎ
암튼 저처럼 삽질 하는 사람(0명) 없길 바라며 글을 씀!
참고
https://velog.io/@songhaeunsong/DFS%EC%99%80-BFS-%EC%96%B8%EC%A0%9C-%EC%93%B8%EA%B9%8C
DFS와 BFS 언제 쓸까?
dfs(깊이 우선 탐색)과 bfs(너비 우선 탐색) 언제 사용하는 게 유리할까?DFS는 한 경로를 따라 최대한 깊게 들어가서 더 이상 갈 곳이 없을 때까지 탐색한다. 그래서 한 경로의 끝까지 탐색한 후 다
velog.io
'코테 연습' 카테고리의 다른 글
| [JS] 프로그래머스 아이템 줍기 (BFS) (2) | 2024.10.08 |
|---|---|
| [JS] 프로그래머스 네트워크 DFS 풀이 (0) | 2024.08.13 |
| [백준온라인/Python] 4673번 셀프 넘버 문제 풀이 (0) | 2022.05.03 |
| [백준온라인/Python] 1546번 평균 문제 풀이 (0) | 2022.05.02 |
| [백준온라인/Python] 3052번 나머지 문제 풀이 (0) | 2022.05.02 |