백트래킹
-
N - QueenAlgorithm with C/BackTracking 2020. 8. 24. 18:19
0. 참고 문헌 1. 문제 2. 문제 분석 퀸은 8가지 방향으로 움직이며 공격을 할 수 있고, 이동 범위도 체스판 전체이다. 8개의 퀸 문제는 8 X 8 크기의 체스판을 염두에 두고 제안됐지만 다른 크기의 체스 판으로도 문제의 확장과 축소가 가능하다. 4 X 4 이상의 크기라면 이 문제를 적용할 수 있는데, 그래서 8개의 퀸 문제를 N 개의 퀸 문제라 부르기도 한다. 퀸을 체스판에 배치할 때, 행을 기준으로 배치하는 것으로 약속을 하도록 하자. 그리고 체스판은 4 X 4로 고정하고 문제 풀이에 접근한다. 당연히 퀸은 하나의 행에 하나만 배치가 가능하다. (퀸의 공격 범위가 가능하므로) 아래의 [그림 1 ~ 4]는 체스판의 크기가 4 X 4일 때의 퀸을 놓는 방법을 나타낸 것이다. 별 모양이 퀸이다. [그..
-
연구활동 가는 길( 인접 행렬 풀이 )Algorithm with C/BackTracking 2020. 8. 19. 19:08
1. 문제 2. 문제 분석 위는 SetDataLoadDataFromFile함수가 호출이 되면, 이차원배열g_Path에 cost가 저장이 된다. cost값이 0이라는 의미를 2가지를 포함하고 있다. 1. 자기 자신에서 자기 자신으로 갈 때의 cost값은 0이다. 2. '길'을 갈 수가 없는 경우에 cost값은 0이다. (현재의 정점과의 연결이 안된 경우) 예를 들어서, g_Path[0][0] = 0 의 의미는 자기 자신에서 자기 자신으로 갈 때의 경우이다. g_Path[1][2] = 0 의 의미는 1번 정점과 2번 정점은 서로 연결되지 않았다는 의미이다, 여기서, 탐색을 할 때 이차원 배열의 행과 열은 다음과 같다. 행 요소 = 현재의 정점 열 요소 = 현재의 정점과 연결된 다음 정점 이를 토대로 다시 설..