Q&A와 스터디
![[레벨:2]](http://old.lameproof.com/modules/point/icons/default/2.gif "포인트:692point (73%), 레벨:2/30"){kind=icon}
우중풍륜미로에서 최단거리 찾는 방법을 알고 싶습니다.
제가 생각하는 방법은
시작점에 예를들어 한마리의 쥐를 집어 넣고
(쥐는 움직이는 경로를 기억합니다.)
갈림길이 발생하면 그 쥐를 복제하고
한곳에서 두 쥐가 만나면 두 쥐중에 더 많은 거리를 움직인 쥐를 죽이고 다른 쥐는 계속 움직이게 둡니다.
가장 빨리 도착점에 나온쥐의 경로가 최단 거리라고 생각 합니다.
많은 방법이 있을거라고 생각하는데 여러분의 생각을 듣고 싶습니다.
제가 생각하는 방법은
시작점에 예를들어 한마리의 쥐를 집어 넣고
(쥐는 움직이는 경로를 기억합니다.)
갈림길이 발생하면 그 쥐를 복제하고
한곳에서 두 쥐가 만나면 두 쥐중에 더 많은 거리를 움직인 쥐를 죽이고 다른 쥐는 계속 움직이게 둡니다.
가장 빨리 도착점에 나온쥐의 경로가 최단 거리라고 생각 합니다.
많은 방법이 있을거라고 생각하는데 여러분의 생각을 듣고 싶습니다.
2007.07.19 14:54:04 (*.196.220.234)
![[레벨:13]](http://old.lameproof.com/modules/point/icons/default/13.gif "포인트:16257point (43%), 레벨:13/30"){kind=icon}
neolith 예상하신 방법이 정답입니다. 자세한 사항은 a-star algorithm 나 path finding 을 검색해보시면 됩니다. 만약 혼자서 상상만으로 저걸 생각해내셨다면 대단하시군요. 참고로 전 고2때 혼자 연습장에 막 끄적거리면서 어떻게 하면 ibm-pc 에서 스프라이트 같은 기능을 구현해낼 수 있을까 생각하다가 더블버퍼링을 생각해냈던 적이 기억나네요
2007.07.19 17:28:19 (*.146.98.184)
죠쨩 걍 저런 알고리즘은 몇가지 간단한 생각으로도 나올수 있지만, 좀더 CS틱한 답변을 원하신다면,
그래프 순회 알고리즘이 기본이되어서, 최단경로 알고리즘(그러니까 디직스트라 알고리즘 정도가 있겠군요)
그거 아니면 아예 백트래킹으로 뽑아보는 방법도 있고.
근데 어차피 생각해보면 그게 그거에요. 약간씩 패러미터를 변경해준다 정도의 느낌으로 보면 되구요.
A*도 뭐 방향성을 고려하고 제한된 연산상황에서 좋을 겁니다. -,.-);
미로는 그냥 한번 쭉따라 가보면 됩니다.
그래프 순회 알고리즘이 기본이되어서, 최단경로 알고리즘(그러니까 디직스트라 알고리즘 정도가 있겠군요)
그거 아니면 아예 백트래킹으로 뽑아보는 방법도 있고.
근데 어차피 생각해보면 그게 그거에요. 약간씩 패러미터를 변경해준다 정도의 느낌으로 보면 되구요.
A*도 뭐 방향성을 고려하고 제한된 연산상황에서 좋을 겁니다. -,.-);
미로는 그냥 한번 쭉따라 가보면 됩니다.
2007.07.20 00:33:04 (*.188.11.193)
우중풍륜 예전에 C로 배우는 알고리즘 책의 우수법, 좌수법 보다가 생각한 겁니다.
학규님 칭찬? 들으니 기분이 좋네요. >_<
학규님 칭찬? 들으니 기분이 좋네요. >_<
2007.07.20 18:57:51 (*.148.192.23)
redThirteen 음.. 한가지 덧붙이자면.. 모든쥐가 자신의 경로를 기억하고 있을 필요는 없습니다.
자기가 온 방향을 미로에 적으면서 가고 목적지에 도착했을때 그 방향을 거꾸로 거슬러 오면됩니다.
그리고 두 쥐가 만나는 경우는 실제로 만나는게 아니라 다른 쥐가 지나간 자리에 도착한 경우를 얘기하겠지요.
이때에 어느 쥐가 더 많이 걸렸나를 판단해 볼 필요없이 나보다 빠른길로 온 쥐가 이미 지나갔기때문에.. 그냥 자살(?)하면 될것같습니다;
자기가 온 방향을 미로에 적으면서 가고 목적지에 도착했을때 그 방향을 거꾸로 거슬러 오면됩니다.
그리고 두 쥐가 만나는 경우는 실제로 만나는게 아니라 다른 쥐가 지나간 자리에 도착한 경우를 얘기하겠지요.
이때에 어느 쥐가 더 많이 걸렸나를 판단해 볼 필요없이 나보다 빠른길로 온 쥐가 이미 지나갔기때문에.. 그냥 자살(?)하면 될것같습니다;
2007.07.20 22:22:17 (*.134.84.91)
neolith 아 참고로 a-star는 목적지랑 직선 거리가 가까운 경우에 좀 더 가중치를 두어서 검색을 효율화해보자라는 취지에서 나온 위 방식의 변형판입니다.
2013.05.19 13:45:53 (*.153.235.115)
![[레벨:3]](http://old.lameproof.com/modules/point/icons/default/3.gif "포인트:962point (24%), 레벨:3/30"){kind=icon}
bestbasci01@yahoo.com
