[프로그래머스 level2] N-Queen - Java

<목차>

1. 문제
2. 접근 방법
3. 풀이 소스

 

[문제]

가로, 세로 길이가 N 인 정사각형으로 된 체스판이 있습니다.

체스판 위의 N개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다.

 

예를 들어서, N = 4 인 경우, 다음과 같이 퀸을 배치하면 N개의 퀸은 서로를 공격할 수 없습니다.

 

 

 

체스판의 가로 세로의 길이 N 이 매개변수로 주어질 때, N 개의 퀸이 조건에 만족 하도록 배치할 수 있는 방법의 수를 return 하는 solution 함수를 완성해주세요.

 

제한사항

• 퀸(Queen)은 가로, 세로, 대각선으로 이동할 수 있습니다.
• n은 12이하의 자연수 입니다.

---

[접근 방법]

1. N = 2 or 3 인 경우는 N 개의 퀸을 배치할 방법이 없음 (무조건 대각선으로 공격하는 배치만 가능함)
2. N = 4 인 경우에 대해 조금 더 파헤쳐보자. (편의상 {1, 1} ~ {4, 4} 로 설명)

 

< {1, 1} / {1, 4} 시작 >

[첫번째 행]

1 열에 퀸을 놓게되면, 좌측 이미지와 같이
1행 / 1열 / 좌하향 대각선 ({2, 2}, {3, 3}, {4, 4}) 에 퀸을 놓을 수 없다.

 

 

[두번쨰 행]

3 열에 퀸을 놓게되면, 3행 어디에 퀸을 위치시키든 2행의 퀸과 서로 공격이 가능해진다. 
=> 탈락
4열에 퀸을 놓게되면, {3, 2} / {4, 3} 자리만 퀸을 놓을 수 있게되며, 두 칸은 서로 공격이 가능하다. => 탈락

 

위 내용은 1,4 에 놓고 시작하는 경우 반대 위치에 동일하게 적용된다.

 

 

 

 

{1, 2} 또는 {1, 3} 에서 시작한다면 다음과 같이 퀸을 배치할 경우 서로 공격하지 않을 수 있다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

위 그림들과 같이, 백트래킹을 활용해 놓을 수 있는 자리와 없는 자리를 케이스를 확인하며 탐색하는 방법이 있으며,

조금이라도 시간을 단축하기 위해 HashSet을 활용하였다.

 

기본적인 탐색의 원칙은 다음과 같다.

• 각 행에는 1개의 퀸만 존재할 수 있다. (겹칠 수가 없으므로 따로 확인하지 않음)
• 각 열에는 1개의 퀸만 존재할 수 있다.
• 각 대각선에는 1개의 퀸만 존재할 수 있다.
  • 여기서 문제는 같은 대각선 상에 퀸이 존재하는지에 대한 판단이다.
    찾은 규칙은 다음과 같다.
    우하향 대각선의 경우, 행과 열의 차가 일정하다. 
    좌하향 대각선의 경우, 행과 열의 합이 일정하다.

 

좌표는 {1, 1} ~ {N, N} 으로 설명하고 있으며, {0, 0} ~ {N-1, N-1} 이여도 동일하다.

---

[풀이 소스]

class Solution {
        int answer;
        public int solution(int n) {
            answer = 0;

            backtracking(new HashSet<Integer>(), new HashSet<Integer>(), new HashSet<Integer>(), 0, n);

            return answer;
        }

        public void backtracking(HashSet<Integer> colSet, HashSet<Integer> leftSet, HashSet<Integer> rightSet, int row, int n) {

            //colSet 	> 컬럼 Set
            //leftSet 	> 좌하향 대각선 Set (row + column)
            //rightSet 	> 우하향 대각선 Set (row - column)

            if(row == n) {
                answer++;
                return;
            } else {
                for(int i = 0; i < n; i++) {

                    if(!colSet.contains(i) && !leftSet.contains(row + i) && !rightSet.contains(row - i)) {
                        colSet.add(i);
                        rightSet.add(row-i);
                        leftSet.add(row+i);
                        backtracking(colSet, leftSet, rightSet, row + 1, n);
                        colSet.remove(i);
                        rightSet.remove(row - i);
                        leftSet.remove(row + i);
                    }
                }
            }
        }
    }