경로에 대한 정보
BFS 설명 하시면서
parent[], distance[] 같은 배열을 추가해서 플레이어가 움직인 정보를 얻을 수 있다고 하셨는데, DFS 이런걸 하지 않는 이유는, DFS에서는 갈 수 있는 경로를 끝까지 다녀 왔다가 길이 더이상 없으면 다시 이전 지점으로 돌아와서 다른 경로의 끝까지 진행하고, 이를 반복하는 특성 때문인가요?
답변 3
5
네 맞습니다.
엄밀히 말해서 BFS, DFS는 특별히 '경로'를 탐색한 단계는 아니고,
그냥 한번씩 모든 노드들을 순회한 것에 가깝습니다.
List같은 경우 0번부터 n번까지 노드들이 순서대로 나열되어 있으니
0번부터 순차적으로 쭉~ 순회하면 그만이지만
그래프의 경우 애당초 노드들이 규칙성 있게 배치된 것이 아니라
중복없이 순회하려면 규칙이 필요한데 그것이 BFS, DFS이라고 볼 수 있습니다.
그리고 BFS나 DFS의 순회 순서를 이용해서 정보를 수집하면
최단거리 등 많은 부가 정보를 얻을 수 있는겁니다.
1
네 맞습니다.
DFS는 처음부터 끝까지 무식하게 파고 들어가니
해당 경로가 최단 경로라는 보장이 없습니다.
반면 BFS는 무조건 시작점을 기준으로 가까운 곳부터 하나씩 탐색을 하게 되니,
어떤 지점을 발견한 순서를 역추적하면
그 경로가 정말 최단 경로라고 장담할 수가 있겠죠.
0
답변 감사드려요
하나 더 여쭤보고 싶은데,
달아 주신 답변을 보고 생각해 본 건데
DFS, BFS는 단순히 경로를 탐색하는거죠?
아직 길을 가는 단계는 아닌거죠?
따져서 말하면, 경로 탐색으로 최단 경로를 찾아서 그 다음에 움직여 나가는거고, 현 강의에서 배운건, 탐색 단계 인거죠?
게임개발에서 주로 어느부분에 알고리즘들이 쓰이는지 궁금합니다
0
170
2
글꼴 바꿔도 자간이 좁아 찌그러져보이시는 분들
0
87
1
NullReferenceException 예외) 같은 실수하시는분 계실까봐 남겨요
0
66
1
parent를 Pos타입으로 만든 이유
0
74
1
콘솔창에 격자가 안나옴 미로 생성 X
0
133
1
격자 생성 안됨 무한루프
0
113
1
BFS 질문
0
143
2
격자 무한 출력
0
166
2
A* 의 PriorityQueue 관련 질문입니다
0
155
2
vscode에서 원그리기
0
179
1
환결설정 강의 원 그리기
0
122
1
15-17분
0
86
1
3:16초에 근데 이렇게 해가지고 부분에 "{}"를 만들어서 자식 node들을 생성하던데 왜 중괄호로 감싸게 만드는 건가요?
0
141
2
동적 배열 관련 질문입니다!
0
209
1
Big-o 표기법에서 시간 복잡도
0
167
1
7:40에서 언급하신 색상이 날아가는 문제 이해를 못하겠습니다
0
151
1
트리구현연습 강의 질문있어요
0
142
1
창은 뜨는데 맵이 나타나지 않아요.
0
174
1
Ctrl F5 하면 나오는 창은 어디서 설정할까요??
0
271
1
void CalcPathFromParent(Pos[,] parent)에 대해서
0
202
2
NullReferenceException예외가 발생했을때 어떻게 해야하나요?
0
228
1
[해결] 환경설정 강의에서 원이 이상하게 그려지는 문제
3
310
2
오른손 법칙에서 플레이어 점이 안 움직입니다
0
243
2
맵 만들기 오류
0
179
1