[프로그래머스 C#] Lv.2 N-Queen

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

프로그래머스

1. 정답코드 및 핵심 아이디어, 유의사항

1) 2차원 배열로 보이는 영역을 1차원 배열로 표현

- 2차원 배열의 y축 좌표와 x축 좌표가 있다고 했을 때, 각 인덱스와 인덱스 안의 값을 y축, x축으로 놓음

 ex) array[index] 라는 배열이 있다면, ( y축 : index, x축 : array[index] 가 되는 것 )

 

2) 대각선에 값이 있는지 체크하는 방법

- 결국 비교대상과 자신을 각 정점으로 봤을 때, 두 정점을 잇는 직선이 y = x 그래프나 y = -x 그래프와 평행한지 판단하면 되므로 기울기의 절댓값이 1이 되는지 확인하면 됨

 -> | y2 - y1 / x2 - x1 | = 1 이 되므로, | x값 증가량 | = | y값 증가량 | 이 됨

 

3) DFS - 백트래킹 ( Back Tracking )

- 유망한 노드라면 탐색을 이어가고 유망하지 않은 노드라면 탐색하지 않고 다음 자식 노드를 탐색하는 백트래킹 알고리즘을 사용해야 함

https://godgjwnsgur7.tistory.com/47

[Algorithm C#] BFS, DFS ( + Back Tracking )

주석 참조

    using System;

    public class Solution
    {
        public int solution(int n)
        {
            int answer = 0;
            var intArray = new int[n]; // y좌표 : index, x좌표 : value
            Function(intArray, 0, n, ref answer);

            return answer;
        }

        // BackTracking DFS
        public void Function(int[] intArray, int currIndex, int n, ref int answer)
        {
            // 끝까지 값을 넣는 데 성공했다면 찾은 것
            if (currIndex >= n)
            {
                answer++;
                return;
            }

            for (int i = 0; i < n; i++)
            {
                intArray[currIndex] = i;

                // BackTracking 조건
                if (IsCheck(intArray, currIndex))
                    Function(intArray, currIndex + 1, n, ref answer);
            }
        }

        // 주어진 조건에 따라 0 ~ currIndex - 1의 값을 currIndex값과 비교하는 메서드
        public bool IsCheck(int[] intArray, int currIndex)
        {
            for (int i = 0; i < currIndex; i++)
            {
                // y축 확인 ( 같은 값이 있다면 같은 y축 좌표에 있는 것 )
                if (intArray[i] == intArray[currIndex])
                    return false;

                // 대각선 확인 ( |x축 증가량| == |y축 증가량| )
                if (Math.Abs(i - currIndex) == Math.Abs(intArray[i] - intArray[currIndex]))
                    return false;
            }

            return true;
        }
    }