Recursion 응용(3)

N Queens Problem

문제

- N X N배열의 체스판에 N개의 말을 서로 동일한 행이나 열에 놓이지 않도록 배치하는 문제

- 문제를 체계적으로 해결하기 위해서는 back tracking기법을 이용하는 것이 좋다.

상태 공간 트리

- 찾는 해를 포함하는 트리이다.

- 해가 존재한다면 그것은 반드시 이 트리의 어떤 한 노드에 해당하고, 따라서 이 트리를 체계적으로 탐색한다면 해를 구할 수 있다.

- 찾고자 하는 해를 위해 반드시 모든 노드를 탐색해야할 필요는 없다. 이는 가능성이 없는 노드는 생략하고 (non-promising, infeasible)탐색을 진행해 효율성을 높일 수 있다는 것을 의미한다.

Back Tracking (되추적 기법)

- 자신이 행했던 경로를 다시 되돌아간다는 것으로 가장 최근에 결정했던 것을 취소하며 새로운 결정으로 수정하는 기법이다.

- 상태 공간 트리를 깊이 우선 방식으로 탐색하여 해를 찾는 알고리즘이다.

순환식으로 생각하기

//매개변수로는 자신이 현재 트리의 어떤 노드에 있는지를 지정해야 한다.

int[] cols = new int[N + 1];

boolean queens (int level) //level변수는 트리의 레벨을 뜻한다.

{

if (!promising(level)) (답일 가능성이 없다면)

return false;

else if (level == N) //promising테스트를 통과했다는 것은 모든 레벨에 말들이 배치되었다는 것으로 답임을 의미한다.

return true;

else //level + 1번째 말을 각각의 열에 놓은 후 recursion을 호출한다.

for (int i = 1; i <= N; i++) {

cols[level + 1] = i;

if (queens(level + 1))

return true;

}

return false;

}

-> 매개변수 level은 현재 노드에서의 레벨을 표현하며 1번에서 level번째 말이 어디에 놓였는지 전역변수인 배열 cols로 표현했다. 

-> cols[i] = j 는 i번째 말이 (i, j)좌표에 놓였음을 의미한다. 이는 곧 i번째 말은 i행에만 배치를 한다는 뜻이 되어 cols배열을 이차원배열로 만들지 않아도 된다는 것을 알 수 있다.

Promising Test

- 현재 level값에 대해서 cols배열의 각 행에 말들을 배치할 때 앞선 level의 값들은 충돌이 없음이 이미 보장되어 있다.

- 마지막에 놓인 말이 이전에 놓인 다른 말들과 충돌하는지만 검사하여 충돌하지 않는 열을 배치하기만 하면 쉽게 정답을 찾아갈 수 있다.

- 구현

boolean promising (int level) {

for (int i = 1; i < level; i++) {

if (cols[i] == cols[level]) //같은 열에 놓였는지 검사

return false;

else if (level - i == Math.abs(cols[level] - cols[i]) ) //같은 대각선에 놓였는지 검사

return false;

}

return true;

}

-> 같은 대각선에 있다는 것은 곧 가로의 거리와 세로의 길이가 같다는 것이다.

-> level - i = |cols[level] - cols[i]|