일단 (0,0)에서 (1,0), (1,1), (0,1)로 가는 경로를 고려해야 할 것이고
(1,0), (1,1), (0,1)에서 각각 (2,0), (2,1), (2,2), (1,2), (0,2)로 가는 경로를 고려해야 할 것이고
이런식으로 (n,n)이 나올 때까지 모두 고려해야겠죠.
가장 단순무식한 알고리즘이라고 하면,
(0,0)에서 시작해서 점들의 리스트를 출력하는데 처음에는 (1,0)으로 가고, (1,0)에서 (1,1)이나 (2,0)으로 가고, ... 이런식으로 그 다음단계로 넘어가는 것을 재귀적으로 탐색하면 됩니다.
1. 한번 지나온 점은 안됨
2. (n,n)으로 끝남
3. 한번에 한 칸씩만 이동
이 규칙을 지키면서 모든 가능성을 탐색하면 됩니다.
2x2매트릭스에서 시작해서 재귀적으로 적용하면
2x2매트릭스에서 시작해서 재귀적으로 적용하면 되겠네요
피할 수 있을때 즐겨라! http://melotopia.net/b
최단 경로가 아니라도 그런식으로 할수 있는건가요?
ㅡㅡㅡ
..........ㅣ
....... ㅡ
......ㅣ
........ㅡ
3x3에 이런 경로같은것도 셈한 수도 재귀적으로 구할수 있는건가요? 제가 알고리즘에 좀 무지해서....... 알고계신다면 설명을 듣고싶습니다!
일단 바둑판 모양의 2차원 격자를 생각하고, 좌상에서
일단 바둑판 모양의 2차원 격자를 생각하고, 좌상에서 우하로 간다고 생각하면,
(0,0)에서 (n,n)으로 가는 경로를 생각해 볼 때
일단 (0,0)에서 (1,0), (1,1), (0,1)로 가는 경로를 고려해야 할 것이고
(1,0), (1,1), (0,1)에서 각각 (2,0), (2,1), (2,2), (1,2), (0,2)로 가는 경로를 고려해야 할 것이고
이런식으로 (n,n)이 나올 때까지 모두 고려해야겠죠.
가장 단순무식한 알고리즘이라고 하면,
(0,0)에서 시작해서 점들의 리스트를 출력하는데 처음에는 (1,0)으로 가고, (1,0)에서 (1,1)이나 (2,0)으로 가고, ... 이런식으로 그 다음단계로 넘어가는 것을 재귀적으로 탐색하면 됩니다.
1. 한번 지나온 점은 안됨
2. (n,n)으로 끝남
3. 한번에 한 칸씩만 이동
이 규칙을 지키면서 모든 가능성을 탐색하면 됩니다.
피할 수 있을때 즐겨라! http://melotopia.net/b
그리고 재귀에 의한 중복을 피하려면
snowall님 말씀대로 일단 재귀로 풀리고 거기에 memoization을 사용하시면 재귀에 의한 중복을 피할 수 있습니다.
윗분들 말씀대로 재귀적으로 풀면 되겠지만..
윗분들 말씀대로 재귀적으로 풀면 되겠지만.. 제가생각할땐
조건이 좀 빠진것 같습니다.
최단경로가 아닌 모든 경로를 구한다면 경로의 경우 수는 무한대가 됩니다.
가다가 뒤로빠져서 가거나, 아니면 싸이클을 만나 빙빙 돌거나 하겠죠.
이런 경우 알고리즘은 존재할 수 없습니다.
무한대의 답을 구하려면 종료될 수 없으니까요.
출발점에서 도착점까지 싸이클이 없는 모든 경로를 구하는 알고리즘이 적절한 것 같습니다.
말씀하신대로 "알고리즘"이라고 한다면 반드시
말씀하신대로 "알고리즘"이라고 한다면 반드시 종료되어야 하니까 조건이 걸려야겠죠.
싸이클이 없는 모든 경로를 구하는 것도 좋지만, 조금 더 느슨한 조건을 걸어본다면 "길이가 k보다 작은 모든 경로"를 구하는 알고리즘 정도를 생각해 볼 수 있을 것 같습니다.
피할 수 있을때 즐겨라! http://melotopia.net/b
조건이 부족했군요. 죄송합니다.......
한번 지난 길은 다시 지나지 않는 모든 경로를 구하는 방법이라고 질문했어야됬었는데...... 그러면 결국 사이클이 존재하지 않는 모든 경로를 구하는 법이 되겠군요.