내가 시간존나 투자해서 알고리즘을 짰어.
제출은 내일 아침이고.
내가 짠 방법은 일단 장기말중에 마가 임의의점 (x,y)로 이동할 수 있는 모든 경로를 조사하고 그 경로중 최소가 되는 경로를 리턴해 주는거야.
근데 판크기를 6x6까지는 이계 계산이 되는데 6x7부터 시간복잡도가 존나게 증가하나봐. 계속 연산하고 안끝난다.... 아시바
판크기는 9x10인데 알고리즘 시간복잡도가 병맛인가봐...
뭔가 단축시킬만한 획기적인 방법이 없을까?
제출은 내일 아침이고.
내가 짠 방법은 일단 장기말중에 마가 임의의점 (x,y)로 이동할 수 있는 모든 경로를 조사하고 그 경로중 최소가 되는 경로를 리턴해 주는거야.
근데 판크기를 6x6까지는 이계 계산이 되는데 6x7부터 시간복잡도가 존나게 증가하나봐. 계속 연산하고 안끝난다.... 아시바
판크기는 9x10인데 알고리즘 시간복잡도가 병맛인가봐...
뭔가 단축시킬만한 획기적인 방법이 없을까?
dp 로해서 어제 설명그림도그려뵛는디 ㅋ [핡]
동적계획법을 어떻게 적용할수있을까요 ㅠㅠ 내꺼는 미로찾기처럼 스택서서 찾아가는건데 여기에 dp를 어떤식으로 적용하면될지 개념좀 심어주세요 ㅜ
악 그림이 있었네... ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ
정 못짜겟으면 어제 생물학 횽이 올린 코드도 잇고 제 블로그 가면 코드도 짜놧음 [핡]
아놔 장기말이 앞으로 한칸 대각선 한칸이동임? 앞한칸 대각선 두칸인줄 알았는뎅... ㅡㅡ;
왠지 재귀 알고리즘으로 depth-first search짜놨을 것 같은 느낌이 든다
breadth-first search로 짜면 좀 더 나을 것 같다. 근데 10x10 해봐야 계산할 노드가 100개 밖에 안되는데 시간이 그케 오래 걸리는거면 좀 이상한데
내가 짜준 예제 코드는 봤냐?
스택말고 큐를 써야해. 그래야 너비 우선 탐색이 되
너비 우선탐색으로 탐색하면 도착지점으로가는 최단 경로에서 가장 먼저 찾으므로 중간에 커팅가능