재귀

[Recursion]재귀: 미로찾기 C#

임의의 시작점에서 정해진 목적지의 출구(Exit)까지 PathWay가 있는지 도출할 수 있을까? 최근 알고리즘 공부를 다시 시작하면서 재귀함수적 사고에 익숙해지려고 연습중에 있다. 이런 이론적인 측면도 공부를 해야 좀 더 다양한 사고가 가능한 것 같다. 실무에 쓰이기는 어려움이 있을 것 같은데 일단 구현력을 갖춘 뒤 선택적 사용을 할 수 있는 것과 전혀 고려 대상이 아닌 것은 확실히 다른 것 같다. 미로찾기는 시작점에서 도착점까지 갈 수 있는지 그리고 그 Pathway는 어떻게 되는지 도출하는 문제이다. 재귀에서 너무 유명한 문제라 풀이 방식이 많지만 최근 회사에서 주로 사용하는 C#으로 풀어보았다. 🎉Recursion 재귀 임의의 시작점에서 (x,y) 출발을 한다 가정했을 때, 임의의 시작점이 Wall..

[Recursion:Backtracking, 깊이우선 탐색 예제] N-Queen C#

N * N 체스판에 최대한 많은 Queen을 놓고 싶다. 다만, 서로를 공격하지 않게 올려놓고 싶다. 총 몇 가지 경우의 수가 있을까? 🎡 BackTracking 백트래킹의 대표적인 문제로 N-Queen으로 공부해보았다. N-Queen이란 N*N의 체스판에서 서로를 잡아먹지 않는 선에서 최대한 많은 수의 퀸을 두는 문제이다. 한 행에는 같은 선상에는 퀸을 1개만 배치할 수 있으므로 N* N배열에서 최대 개수는 N개가 될 것이다. 이것의 위치를 한정조건 없이 탐색할 경우 엄청나게 많은 조합의 경우가 탄생한다(O(N^N)). 첫 행에 체스말을 배치시켰을 경우 그 다음행에서 배치말이 유효한 칸이 있는지(둘 수 있는 칸인지) 검사 한뒤 없다면 이를 배제하고 그 전 행으로 되돌아간 뒤 , 다음 노드를 검사한다. ..