프로그래머스 - N-Queen

leehyunjon·2022년 12월 20일

백트래킹 프로그래머스

Algorithm

목록 보기

147/162

N-Queen : https://school.programmers.co.kr/learn/courses/30/lessons/12952

Problem

Solve

2차원 배열로 완전탐색을 이용하여 문제를 구현하려하였으나, 시간초과와 구현이 잘 되지 않아서 다른분의 풀이를 참고하였습니다.

일단 2차원 배열을 1차원 배열로 압축하는것이 인상적인 풀이였습니다.
2차원 배열에서 Q가 존재하는 위치를 1차원배열의 index를 Q가 존재하는 행, 존재하는 값이 열로 표현할 수 있었습니다.

해당 2차원 배열같은 경우 [1, 3, 0 ,2]로 나타낼수 있습니다.

0행에는 1열에 Q 존재
1행에는 3열에 Q 존재
2행에는 0열에 Q 존재
3행에는 2열에 Q 존재

그렇다면 0행부터 n-1행까지 백트래킹을 통해 각 열에 Q를 넣고 해당 행,열에 Q가 들어간다면 퀸이 서로 만나는 여부를 판단하면 문제를 해결할 수 있습니다.

void setQueen(int row, int n){
	//행을 모두 만족한다면 Q이 서로 공격할수 없는 경우가 완성됩니다.
	if(row == n){
		answer++;
		return;
	}
        
	//해당 행에서의 열을 모두 선택하여 조건을 만족하는지 확인합니다.
	for(int col=0;col<n;col++){
		queens[row] = col;
		if(check(row)){
        	//해당 행, 열이 조건을 만족한다면 백트래킹을 통해 다음 행을 진행합니다.
			setQueen(row+1, n);
		}
	}
}

Q가 서로 만나는 여부를 판단하기 위해서는 두가지 방법이 있습니다.

먼저 특정 행보다 이전의 행의 열이 중복되지 않아야 합니다.
이는 0부터 특정 행 전까지의 1차원 배열의 값을 비교하여 알 수 있습니다.

두번째 현재 행과 열의 값과 특정 행과 열의 값의 기울기가 1이 되지 않아야 합니다.
기울기가 1이되는것은 대각선으로 만나게 됨을 의미하게 됩니다.
두 좌표에서의 기울기는 x1-x2/y1-y2 = 1의 공식으로 구할수 있습니다. 두 좌표를 비교하기 위해 x1-x2 = y1-y2여부로 기울기가 1이 됨을 확인하여 두 행과 열이 조건을 만족하는지 확인합니다.

//비교할 현재 행
boolean check(int row){
	//0부터 현재 행의 전과 비교
	for(int i=0;i<row;i++){
    	//두 열이 동일하다면 Q는 만나게됩니다.
		if(queens[row] == queens[i]) return false;
        //절대값으로 열의 차와 행의 차가 동일하면 Q는 만나게됩니다.
		if(Math.abs(queens[row]-queens[i]) == Math.abs(row-i)) return false;
	}
	return true;
}

Code

class Solution {
    int[] queens;
    int answer;
    public int solution(int n) {
        queens = new int[n];
        answer = 0;
        setQueen(0,n);
        return answer;
    }
    
    void setQueen(int row, int n){
        if(row == n){
            answer++;
            return;
        }
        
        for(int col=0;col<n;col++){
            queens[row] = col;
            if(check(row)){
                setQueen(row+1, n);
            }
        }
    }
    
    boolean check(int row){
        for(int i=0;i<row;i++){
            if(queens[row] == queens[i]) return false;
            if(Math.abs(queens[row]-queens[i]) == Math.abs(row-i)) return false;
        }
        return true;
    }
}