백트래킹 - NQueen

NQueen 문제풀이

- N*N의 체스판에서 모든 행에 대해서 각 행마다 하나의 퀸이 존재하도록 퀸을 배치하는 문제

조건

1. 모든 행에 대해서 각 행마다 하나의 퀸이 존재

2. 각 퀸은 같은 열 또는 대각선 상에 위치할 수 없음

풀이전략

먼저 5시간 정도 삽질한 내용을 적자면 ( 하.. 부끄럽다 .. )

(1). 체스판을 2차원 배열로 표현

(2). 퀸을 체스판(2차월 배열)에 위치시킬 수 있는지 검사( 배열 전체를 검사함 - 같은 행, 같은 열, 대각선상에 존재 )

(3). 위치시킬 수 있다면 체스판의 값을 업데이트 ( 2 - 퀸의 위치, 1 - 퀸을 놓을 수 없는 위치, 0 - 퀸을 놓을 수 있는 위치 )

(4). 다음 행의 노드 전부를 2번에서 구한 노드의 자식노드로 설정

(5). 자식 노드를 순회하며 (2)~(4) 번  순회

# 자식 노드 전부 퀸을 위치시킬 수 없다면 ? 

 - (2)의 수행결과를 롤백해야 함

 - 부모의 퀸을 +1열 옮겨서 다시 테스트해야함 ( 이부분에 대해 스택으로 삽질해보았지만 머리만 아팠다..)

접근 방법이 잘못되었다고 느끼기 시작했다... 

힌트를 얻고자 구글링하다가 친절하게 설명해주신 분을 발견 !!  감사합니다 ㅠㅠ

( https://bumbums.tistory.com/3 )

핵심을 말하자면 2차원 배열로 퀸의 위치를 표현하는 것이 아니라

행의 크기(N) 와 각 행에서의 퀸의 위치(cols)를 1차원 배열로 표현하여 분리해야 한다는 것 !

구현하기

/**
 * @author troh
 */
public class Stack백트래킹_NQueen {
    private static int N = 4;
    private static int[] cols;
    
    public static void main(String[] args) {
        cols = new int[4];
        backTracking(0);
    }
    
    public static void backTracking(int level) {
        // 현재 레벨이 N이라는 것은 N-1까지 퀸을 배치했다는 것이므로 모든 퀸을 배치 완료했다는 것
        // 답을 출력
        if(level == N) {
            for(int i=0; i<N; i++) {
                System.out.printf("%d ", cols[i]);
            }
            System.out.println("");
        } 
        // 현재 레벨의 어느 위치에 퀸을 두어야 하는지 확인
        else {    
            for(int i=0; i<N; i++) {
                // 현재 레벨의 퀸은 i열에 위치시킴
                cols[level] = i; 
                // 현재 레벨이 유효한지 검사
                if(isPossible(level)) {
                    backTracking(level+1);
                }
            }
        }
    }
    
    public static boolean isPossible(int level) {
        for(int i=0; i<level; i++) {
            // 같은 열에 위치하거나
            // 또는
            // 대각선에 위치하거나 ( 가로차이와 세로차이가 같으면 대각선상에 있다고 판단 )
            if(cols[i] == cols[level] || Math.abs(level-i) == Math.abs(cols[level] - cols[i])) {
                return false;
            }
        }
        return true;
        
    }
}
 

배운점 ..

5시간의 삽질로 인해 스택과 재귀함수에 대해 많이 생각해 본 것 같다. 그리고 알고리즘 구현에 잡다한 로직(2차원 배열의 수행결과 롤백)을 수행해야 한다면 문제를 다른 시각으로 생각해봐야 할 것 같다.