인프런 커뮤니티 질문&답변
작성한 질문수
BFS 질문
작성
·
124
·
수정됨
0
bfs는 최단거리를 어떻게 찾는건지 이해가 안되서 질문 남깁니다. 그니까 여러 갈래의 길을 부모-자식의 관계로 뻗어나가면서 찾다가, 도착점에 도달하는 부모자식 관계가 있으면, 부모를 타고 올라가면서 확인 한 다음에 reverse를 시켜서 다시 부모에서 자식으로 내려간다고 이해하면 될까요
답변 2
0
0
안녕하세요, 인프런 AI 인턴입니다. mint4797님.
BFS(너비 우선 탐색)는 그래프나 트리에서 최단 경로를 찾는 데 효과적인 알고리즘입니다. BFS는 시작 위치에서 가능한 모든 이웃 노드를 탐색하고, 이 노드들에서 다시 주변의 노드를 탐색하는 방식으로 진행됩니다. 이 과정을 통해 차례로 모든 경로를 탐색하므로, 특정 지점에 가장 빨리 도달할 수 있는 최단 경로를 찾을 수 있게 됩니다.
큐를 통한 탐색: BFS는 큐를 사용하여 탐색 경로를 관리합니다. 시작 지점에서 출발하여 인접한 노드들을 큐에 저장하고, 각 노드를 차례로 방문하면서 그 노드와 인접한 노드들을 다시 큐에 추가합니다.
많은 경로 중 최단 경로: BFS는 모든 가능한 경로를 동시에 확장해 나가며, 처음으로 목적지에 도달하는 탐색 경로가 최단 경로가 됩니다. 즉, 탐색 도중 벽이나 막힌 지점이 나올 경우, 다른 경로들로 탐색을 계속 진행합니다. 이 때문에 BFS는 항상 최단 경로만 남게 되는 것입니다.
관련된 질문들이 많이 올라와 있어 몇 가지를 추천드립니다:
- BFS 에 대해서 - BFS의 경로 탐색 방식에 대한 기본적인 이해를 돕습니다.
- 최단 경로 판단에 대하여 - BFS가 어떻게 최단 경로를 찾는지에 대한 보다 자세한 설명이 있습니다.
- BFS 관련 질문드립니다. - BFS가 실제로 어떻게 동작하는지에 대한 개념을 설명합니다.
위의 추천된 게시물들을 통해 BFS의 작동 방식을 이해하고, 특히 큐를 사용하는 이유와 최단 경로를 보장할 수 있는 원리를 배울 수 있을 것입니다.
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다. 현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.