거슬러 올라가는 이유
359
작성한 질문수 7
제가 이해한게 맞는지 궁금해서 질문드립니다.
마지막 도착점에서 역산하여 포지션 리스트를 만들어 나가는 과정이 처음에는 왜 필요한지 의문이었는데 왜냐면 저는
처음에 언뜻 생각했을 때는 길 좌표를 BFS로 만들어 나가는 과정인 for문에서 _points 리스트를 추가해 나가면 될 거라고 생각했기 때문입니다.
그런데 다시 생각해보면 BFS 는 끝이 막힌 형태의 경로를 여러 갈래 찾아낼테고 그 여러 경우 중 마지막 점에 도착하는 경우가 필요했기 때문에 마지막 도착점에서 역산하는 과정이 필연적으로 들어가야 했다고 해석했습니다.
이게 맞을까요?
만약 맞다면 최종점의 좌표를 어느곳으로 바꿔도 그에 따른 새로운 해법이 생길거라고 예상이 되는데 이것도 맞나요?
답변 2
0
이해하신게 맞습니다.
for 문에서 points 리스트를 추가하는 것은
BFS 자체가 서칭한 경로 순서이지만,
BFS는 처음부터 목적지로 향한 최단거리 길로 향해서 서칭한다는 보장이 없습니다.
우리가 원하는건 목적지에 도착했을 때의 최단거리를 추출하고 싶기 때문에 역산 과정이 필요한 것입니다.
최종점을 어느 곳으로 바꾸더라도 BFS가 끝나고 나면
길이 있는지, 최단거리는 무엇인지 답은 무조건 나오게 됩니다.
게임개발에서 주로 어느부분에 알고리즘들이 쓰이는지 궁금합니다
0
170
2
글꼴 바꿔도 자간이 좁아 찌그러져보이시는 분들
0
86
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
140
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
308
2
오른손 법칙에서 플레이어 점이 안 움직입니다
0
243
2
맵 만들기 오류
0
178
1