20240227_N-Queen(프로그래머스)

오늘의 TIL은 N-Queen이라는 프로그래머스의 문제에 대한 내용이다.

 

문제 링크

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

프로그래머스

 

문제 설명

가로, 세로의 길이가 n인 정사각형으로 된 체스판이 있다.

체스판 위의 n개의 퀸이 서로 공격할 수 없도록 배치하려고 한다.

체스판의 가로, 세로의 길이 n, n개의 퀸이 조건이 만족하도록
배치할 수 있는 방법의 수를 return 하시오.

 

 

제한 조건

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

 

 

해결 방안

1. 백트래킹 방안을 사용할 예정으로 전역 변수들을 선언한다.

2. 이전에 퀸을 놓은 경우에 다음 퀸이 위치할 수 있는지 판단하는 bool을 선언

3. 재귀함수를 이용하여 퀸을 하나씩 배치. 배치가 끝나면 answer++

 

 

통과한 답안

using System;

public class Solution {
    private int[] board;
    private int answer;
    private int size;
    
    public int solution(int n) {
        answer = 0;
        size = n;
        board = new int[n];
        SolveNQueen(0);      
        return answer;
    }
    public bool IsSafe(int row, int col)
    {
        for (int i = 0; i < row; i++)
        {
            if (board[i] == col || Math.Abs(board[i] - col) == Math.Abs(i - row))
            {
                return false;
            }
        }
        return true;
    }

    public void SolveNQueen(int row)
    {
        if (row == size)
        {
            answer++;
            return;
        }

        for (int col = 0; col < size; col++)
        {
            if (IsSafe(row, col))
            {
                board[row] = col;
                SolveNQueen(row + 1);
            }
        }
    }    
}

 

 

전역 변수 설정과 solution 실행

private int[] board;
private int answer;
private int size;

public int solution(int n) {
    answer = 0;
    size = n;
    board = new int[n];
    SolveNQueen(0);      
    return answer;
}

 

함수들에서 사용할 전역 변수를 설정한다(board, answer, size).

 

변수들의 값을 지정하고 SolveNQueen 함수를 실행한다.

 

얻은 answer의 값을 반환한다.

 

 

Queen을 놓을 수 있는 장소가 있는지 판단

public bool IsSafe(int row, int col)
    {
        for (int i = 0; i < row; i++)
        {
            if (board[i] == col || Math.Abs(board[i] - col) == Math.Abs(i - row))
            {
                return false;
            }
        }
        return true;
    }

 

bool 값을 진행하면서 board에 주어진 row와 col에 대해서 해당 위치가 Queen을 놓을 수 있는 장소인지 판단한다.

가로, 세로, 대각선에 다른 퀸이 있는지 판단하고 배치가 가능하면 true를 반환하게 만들었다.

 

 

재귀함수를 이용한 N-Queen의 가능한 수 구하기

public void SolveNQueen(int row)
{
    if (row == size)
    {
        answer++;
        return;
    }

    for (int col = 0; col < size; col++)
    {
        if (IsSafe(row, col))
        {
            board[row] = col;
            SolveNQueen(row + 1);
        }
    }
}

 

col을 0에서부터 시작하여 Queen을 놓을 수 있는 자리가 있다면 그 위치에 퀸을 배치하고(borad[row] = col)

 

다음 행에 대해서 Queen을 놓을 수 있는 자리가 있는지 판단하는 SolveNQueen(row + 1)을 수행한다.

 

최종적으로 row == size가 된다면 모든 퀸을 성공적으로 배치한 것이므로 answer++하는 것으로 횟수를 추가한다.

 

이 answer가 최종적으로 가능한 N-Queen의 배치의 수가 된다.

 

 

오늘은 N-Queen 문제를 풀면서 백트래킹이라는 단어를 알게 되어서 이를 통해서 백트래킹을 공부하려고 하였으나,

 

시간이 부족하여 백트래킹을 자세히 정리하지 못했지만, 우선적으로 이 문제를 정리했다.

 

추후에 백트래킹에 대한 내용을 다시 정리하면서 추가로 문제를 풀어보고자 한다.

 

아래는 백트래킹에 대한 간략한 내용 정리이다.

 

백트래킹의 특징

효율성

백트래킹은 모든 가능한 경우의 수 중에서 조건을 만족하는 모든 해를 찾아내지만, 조건을 만족하지 않는 경우에는 조기에 포기하여 불필요한 탐색을 줄인다. 이는 완전 탐색보다 훨씬 효율적인 경우가 많다.

-> 위의 함수에서 IsSafe를 통해서 끊어내는 과정

 

재귀적 구조

대부분의 백트래킹 알고리즘은 재귀적 구조로 구현된다. 각 재귀 호출은 하나의 결정을 내리고, 그 결정이 가능하지 않다고 판단되면 다른 결정을 시도하기 위해 재귀 호출을 종료(백트랙)한다.

-> SolveNQueen 함수 속에 SolveNQueen 이 들어있는구조

 

가지치기(Pruning)

백트래킹 알고리즘의 핵심은 가능하지 않은 노드를 빠르게 식별하고 탐색하지 않는 "가지치기" 과정이다.

이를 통해서 탐색 공간을 대폭 줄일 수 있다.

 

 

백트래킹 사용 사례

백트래킹이 주로 사용되는 문제는 아래와 같다.

1. N-Queen 문제

N x N 체스판 위에 N개의 퀸을 서로 공격할 수 없게 배치하는 모든 경우의 수를 찾는 문제

 

2. 순열과 조합 문제

주어진 요소들로부터 모든 가능한 순열이나 조합을 찾는 문제

 

3. 해밀턴 경로와 오일러 경로 문제

그래프 이론에서, 모든 정점을 정확히 한 번씩 방문하는 경로(해밀턴 경로)나

모든 간선을 정확히 한 번씩 거치는 경로(오일러 경로)를 찾는 문제

 

4. 서브셋 합 문제

주어진 숫자 집합에서 몇몇 숫자를 선택해 특정 합을 만들 수 있는지를 결정하는 문제

 

백트래킹 vs 다이나믹 프로그래밍

백트래킹과 다이나믹 프로그래밍은 모두 최적화 문제와 결정 문제를 해결하기 위해 사용되지만, 접근 방식에서 차이가 있다. 다이나믹 프로그래밍은 주로 중복 계산을 피하기 위해 이전에 계산된 결과를 저장하며 사용하는 반면, 백트래킹은 가능한 모든 해를 시도하되, 유망하지 않은 경로는 조기에 포기하여 탐색 공간을 줄이는데 초점을 맞춘다.

때로는 두 기법이 함께 사용되는 경우도 있다.