C# N-Queen - 백트레킹 순열 / 프로그래머스 [Lv.2]

출처: 프로그래머스 코딩 테스트 연습
https://school.programmers.co.kr/learn/courses/30/lessons/12952

 

 

1차 시도

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

    // 한 줄에 한개의 퀸만 들어갈 수 있다.
    // 우선 0 ~ n - 1 로 만들 수 있는 순열을 만든다.
    int[] arr = Enumerable.Range(0, n).ToArray();
    var list = new List<int[]>();
    Perm(list, arr, 0, n, n);

    // 퀸은 자신의 위치에서 가로가 k차이 나면 세로 절대값 k차이는 같이 배치될 수 없다.
    foreach(int[] nums in list)
    {
        if(IsValid(nums, n))
            ++answer;
    }

    return answer;
}

private bool IsValid(int[] array, int n)
{
    for(int x = 0; x < n; ++x)
    {
        for(int k = 1; k < n; ++k)
        {
            if(x + k < n)
            {
                if(Math.Abs(array[x] - array[x + k]) == k)
                    return false;
            }
        }
    }
    return true;
}

private void Perm(List<int[]> list, int[] arr, int depth, int n, int k)
{
    if(depth == k)
    {
        list.Add(arr.Clone() as int[]);
        return;
    }

    for(int i = depth; i < n; ++i)
    {
        Swap(arr, i, depth);
        Perm(list, arr, depth + 1, n, k);
        Swap(arr, i, depth);
    }
}

private void Swap(int[] arr, int a, int b)
{
    int temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}

1. 십자 형태 제외하기

 - 세로줄 당 하나의 퀸이 들어갈 수 있음.

 - 0 ~ n -1 로 순열을 만들기로 함.

 

2. 대각선 형태 제외하기

 - 가로가 k만큼 차이날 때 y도 k만큼 차이 나면 대각선이니 제외한다.

 

2차 시도

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

    // 한 줄에 한개의 퀸만 들어갈 수 있다.
    // 0 ~ n - 1 로 만들 수 있는 순열을 만들고 체크.
    int[] arr = Enumerable.Range(0, n).ToArray();
    Perm(arr, 0, n, ref answer);

    return answer;
}

private void Perm(int[] arr, int depth, int n, ref int answer)
{
    if(depth == n)
    {
        if(IsValid(arr, n))
            ++answer;

        return;
    }

    for(int i = depth; i < n; ++i)
    {
        Swap(arr, i, depth);
        Perm(arr, depth + 1, n, ref answer);
        Swap(arr, i, depth);
    }
}

private void Swap(int[] arr, int a, int b)
{
    int temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}

// 가로가 k만큼 차이날 때 y도 k만큼 차이나면 대각선이니 제외한다.
private bool IsValid(int[] array, int n)
{
    for(int x = 0; x < n; ++x)
    {
        for(int k = 1; k < n - x; ++k)
        {
            if(Math.Abs(array[x] - array[x + k]) == k)
                return false;
        }
    }
    return true;
}

약간의 최적화 시도. 별도로 리스트에 담지 않고 바로바로 IsValid를 체크하도록 했다.

거의 시간이 절반으로 줄었지만, 11번 테스트는 아마 최대치 (n = 12) 인 듯하다.

 

 

나의 풀이

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

    // 한 줄에 한개의 퀸만 들어갈 수 있다.
    // 0 ~ n - 1 로 만들 수 있는 순열을 만들고 체크.
    int[] arr = Enumerable.Range(0, n).ToArray();
    Perm(arr, 0, n, ref answer);

    return answer;
}

private void Perm(int[] arr, int depth, int n, ref int answer)
{
    if(depth == n)
    {
        ++answer;
        return;
    }

    for(int i = depth; i < n; ++i)
    {
        Swap(arr, i, depth);

        if(IsValid(arr, depth))
            Perm(arr, depth + 1, n, ref answer);

        Swap(arr, i, depth);
    }
}

private void Swap(int[] arr, int a, int b)
{
    int temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}

// 가로가 k만큼 차이날 때 y도 k만큼 차이나면 대각선이니 제외한다.
// 아직 depth까지만 채워져 있기때문에 가로줄 기준 depth까지만 체크해도된다.
private bool IsValid(int[] arr, int depth)
{
    for(int x = 0; x < depth; ++x)
    {
        if(Math.Abs(x - depth) == Math.Abs(arr[x] - arr[depth]))
            return false;
    }
    return true;
}

순열을 다 만들고 IsValid 체크하는 게 아니고, 

가지를 만들기 전에 우선 체크해서 필요 없는 부분을 제거하는.. A*의 휴리스틱 같은 느낌.   

아무래도 재귀다 보니 체크를 먼저 해주면 성능이 극적으로 향상된다.

 

 

 

다른 사람 풀이

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

    // 한 줄에 한개의 퀸만 들어갈 수 있다.
    var arr = new int[n];
    BackTracking(arr, 0, n, ref answer);

    return answer;
}

private void BackTracking(int[] arr, int depth, int n, ref int answer)
{
    if(depth == n)
    {
        ++answer;
        return;
    }

    for(int i = 0; i < n; ++i)
    {
        arr[depth] = i;

        if(IsValid(arr, depth))
            BackTracking(arr, depth + 1, n, ref answer);
    }
}

// depth까지만 계산한다.
private bool IsValid(int[] array, int depth)
{
    for(int x = 0; x < depth; ++x)
    {
        if(array[x] == array[depth]) return false;
        if(Math.Abs(array[x] - array[depth]) == Math.Abs(depth - x)) return false;
    }
    return true;
}

백트레킹 방식으로 풀이.

내가 풀었던 순열 자체도 백트레킹의 일종이라서 비슷하다.

 

성능은 비슷하겠지만 이쪽이 좀 더 간결하기 때문에 다음엔 백트레킹 쪽으로 풀어야겠다.