BFS 질문
143
2 asked
bfs는 최단거리를 어떻게 찾는건지 이해가 안되서 질문 남깁니다. 그니까 여러 갈래의 길을 부모-자식의 관계로 뻗어나가면서 찾다가, 도착점에 도달하는 부모자식 관계가 있으면, 부모를 타고 올라가면서 확인 한 다음에 reverse를 시켜서 다시 부모에서 자식으로 내려간다고 이해하면 될까요
Answer 2
0
안녕하세요, 인프런 AI 인턴입니다. mint4797님.
BFS(너비 우선 탐색)는 그래프나 트리에서 최단 경로를 찾는 데 효과적인 알고리즘입니다. BFS는 시작 위치에서 가능한 모든 이웃 노드를 탐색하고, 이 노드들에서 다시 주변의 노드를 탐색하는 방식으로 진행됩니다. 이 과정을 통해 차례로 모든 경로를 탐색하므로, 특정 지점에 가장 빨리 도달할 수 있는 최단 경로를 찾을 수 있게 됩니다.
큐를 통한 탐색: BFS는 큐를 사용하여 탐색 경로를 관리합니다. 시작 지점에서 출발하여 인접한 노드들을 큐에 저장하고, 각 노드를 차례로 방문하면서 그 노드와 인접한 노드들을 다시 큐에 추가합니다.
많은 경로 중 최단 경로: BFS는 모든 가능한 경로를 동시에 확장해 나가며, 처음으로 목적지에 도달하는 탐색 경로가 최단 경로가 됩니다. 즉, 탐색 도중 벽이나 막힌 지점이 나올 경우, 다른 경로들로 탐색을 계속 진행합니다. 이 때문에 BFS는 항상 최단 경로만 남게 되는 것입니다.
관련된 질문들이 많이 올라와 있어 몇 가지를 추천드립니다:
- BFS 에 대해서 - BFS의 경로 탐색 방식에 대한 기본적인 이해를 돕습니다.
- 최단 경로 판단에 대하여 - BFS가 어떻게 최단 경로를 찾는지에 대한 보다 자세한 설명이 있습니다.
- BFS 관련 질문드립니다. - BFS가 실제로 어떻게 동작하는지에 대한 개념을 설명합니다.
위의 추천된 게시물들을 통해 BFS의 작동 방식을 이해하고, 특히 큐를 사용하는 이유와 최단 경로를 보장할 수 있는 원리를 배울 수 있을 것입니다.
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다. 현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.
게임개발에서 주로 어느부분에 알고리즘들이 쓰이는지 궁금합니다
0
171
2
글꼴 바꿔도 자간이 좁아 찌그러져보이시는 분들
0
88
1
NullReferenceException 예외) 같은 실수하시는분 계실까봐 남겨요
0
66
1
parent를 Pos타입으로 만든 이유
0
74
1
콘솔창에 격자가 안나옴 미로 생성 X
0
133
1
격자 생성 안됨 무한루프
0
114
1
격자 무한 출력
0
167
2
A* 의 PriorityQueue 관련 질문입니다
0
155
2
vscode에서 원그리기
0
180
1
환결설정 강의 원 그리기
0
122
1
15-17분
0
87
1
3:16초에 근데 이렇게 해가지고 부분에 "{}"를 만들어서 자식 node들을 생성하던데 왜 중괄호로 감싸게 만드는 건가요?
0
141
2
동적 배열 관련 질문입니다!
0
209
1
Big-o 표기법에서 시간 복잡도
0
167
1
7:40에서 언급하신 색상이 날아가는 문제 이해를 못하겠습니다
0
151
1
트리구현연습 강의 질문있어요
0
142
1
창은 뜨는데 맵이 나타나지 않아요.
0
175
1
Ctrl F5 하면 나오는 창은 어디서 설정할까요??
0
271
1
void CalcPathFromParent(Pos[,] parent)에 대해서
0
202
2
NullReferenceException예외가 발생했을때 어떻게 해야하나요?
0
229
1
[해결] 환경설정 강의에서 원이 이상하게 그려지는 문제
3
311
2
오른손 법칙에서 플레이어 점이 안 움직입니다
0
245
2
맵 만들기 오류
0
179
1
맵 만들기 부분 오류
0
236
1