백트랙킹backtracking

제약조건 만족 문제에서 해를 찾기 위한 전략
해를 찾기 위해 후보군에 제약조건을 체크하고 실패한 대상은 체크하고 다른 후보 찾는다
상태공간트리 사용해서 고려할 수 있는 경우의 수 표현
DFS 방식으로 탐색
뭔말을 이렇게 어렵게 설명하는지..

백트랙킹은 개념적으로 트리구조를 사용한다고 한다 트리에서 DFS 로 탐색한다고 해보자 A - B - D - E 이런식으로 탐색하는데

D, E 가 제약조건을 만족하지 않으면 B,D,E를 제외한다는 것이다

N Queen문제
N은 입력받는 수 이다
N x N 의 체스판을 만들고 N개의 퀸을 배치하는 문제이다
이때 퀸은 서로 공격할 수 없어야 한다
다음고 같이 퀸을 배치 할 수 있다

체스판을 인덱싱하고 트리구조로 개념적으로 처리한다고 해보자

대충 이런 모양의 트리가 4개나 된다. 개당 64 * 4 = 256 가지의 경우가 나온다

0.0 을 루트노드로 시작하면 퀸을 3개까지만 가능해서 답이 안나오므로..

다음 0.1을 루트노드로 하는 트리에서 탐색을 한다

그리고 1.0 1.1 1.2 노드는 제외된다 0.1퀸의 공격범위에 들어가니까. 이제 1.3 노드밑으로 탐색하면된다

2.1, 2.2, 2.3 노드도 0.1과 1.3퀸의 공격범위에 들어가므로 제외한다

이런식으로 반복이다

일단 이론만 듣고 구동 되는 코드를 만들긴 했다...;; 3시간 가까이 걸렸다. 이론이 어려운게 아닌데 구현하다보니 막혀서 시간이 오래 걸렸다

Position클래스를 만들어서 사용했다

public class Position {
    public Integer x;
    public Integer y;

    Position(Integer x, Integer y)
    {
        this.x = x;
        this.y = y;
    }

    @Override
    public boolean equals(Object obj) {
        return (this.x == ((Position)obj).x && this.y == ((Position)obj).y);
    }

    @Override
    public String toString() {
        return "("+ x + "," + y + ")";
    }
}

public class NQueen {

    boolean isSafe(Position curpos, ArrayList<Position> queens, Integer n)
    {
        if(curpos.x >= n || curpos.y >= n)
            return false;

        if(queens.contains(curpos))
            return true;

        boolean result = true;

        for(Position queen : queens)
        {
            if(curpos.x == queen.x || curpos.y == queen.y)
                return false;
            if(queen.x - queen.y == curpos.x - curpos.y)//rising line
                return false;
            if(queen.x + queen.y == curpos.x + curpos.y)//downing line
                return false;
        }

        return result;
    }

    ArrayList<Position> dfsFunc(Integer n)
    {

        ArrayList<Position> stack = new ArrayList<>();
        ArrayList<Position> queens = new ArrayList<>();

        int rootcount = 0;

        while(rootcount < n)
        {
            stack.clear();
            queens.clear();

            stack.add(new Position(0, rootcount));
            queens.add(new Position(0, rootcount));
            rootcount++;

            int y = 0;
            while(stack.isEmpty() == false)
            {
                Position curpos = stack.get(stack.size()-1);
                Position childpos = new Position(curpos.x+1, y);

                if(isSafe(childpos, queens, n))
                {
                    stack.add(childpos);
                    queens.add(childpos);
                    y = 0;
                }
                else
                {
                    y++;
                    if(y >= n)
                        stack.remove(stack.size()-1);

                    if(childpos.x >= n)
                        break;
                }
            }

            if(queens.size() == n)
                break;
        }


        return queens;
    }
}

public class NQueenTest {
    public static void main(String[] args) {
        NQueen nq = new NQueen();

        ArrayList<Position> result = nq.dfsFunc(4);

        System.out.println(result);
    }
}