N Queeens

各アルゴリズムを理解)BF/DFS/Backtraking

データ構造の再帰を理解し、ツリー(+図)

問題タイプ)N-Queens問題

の問題について)N-Queens

精選草、多種草

🔥 1. BF/ DFS/ Backtraking

1.Brute(無知)+Force(パワー)

ルート・ツリーは、可能な限り任意の数のデータをナビゲートし、条件に合致する結果のみを取得できる完全なナビゲーション・アルゴリズムです.これは無知で結果を探す方法なので、100%正解を見つけることができます.

「一つ以上の太陽」仮定、全領域

を探索

はすべての資料を閲覧する必要があるため、各構造には異なる方法がある.

すべての

線形構造を参照するには、

を順に参照します.
すべての

非線形構造を参照するには、幅優先探索/キュー(BFS)、深さ優先探索/スタック(DFS)

を使用します.

2.DFS（深度優先ナビゲーション）

接続ノードの優先度に基づいて最大限深く進む方法

そのため、事前に切断したり、不要なルートを取ったりするなどの行動がないため、状況の数を減らすことはできません.

ブラウズ時にどのノードにアクセスしたかを確認する必要があります.チェックしないと無限ループに陥ります.

解題方法:反復(stack)、再帰

3.遡及（backtracking）

可能な限り、特定の条件を満たす場合にのみ表示されます.

つまり、答えが可能かどうかを判断し、そうでなければ探索せず、その部分に枝を切る.

n=1,n=2,n=3ノードは有害か否かを下向きに判断し,希望がないと判断した場合,そのノードの前(親)ノードに戻って逆方向追跡を行う.

主に問題解では,DFSなどによってすべての場合に答えが見つからない場合を定義し,条件文などによって答えを定義することは絶対に不可能である場合を定義し,この場合は探索を停止して前の場合に戻り,他の場合の探索を再開する.

再帰的使用はDFSに似ている

答えになる可能性があるなら希望があると言い、希望のないノードに行かないことを枝切りと言います.

どれだけうまく剪定するかは効率にかかっている.

N-Queens
1)どのように「希望性(答えになる可能性がある)」を測るか
2)希望がなければどのように枝切りをするか(不可能な可能性を探る)

🔥 2.データ構造）再帰、Graph、tree

1. recursion

void Recursive(void)
{
  printf("Recursive call! \n");
  Recursive();  # 나자신 호출
}

# 재귀함수: 다음과 같이 함수 내에서 자기 자신을 다시 호출하는 함수를 의미
# Q) 완료되지 않은 함수를 다시 호출하는 것이 가능한가요!? 
# A) 네! recursive 함수가 호출되면, recursive 함수의 복사본이 만들어져서 복사본이 실행되는 구조이기 때문입니다!

# 재귀의 탈출 조건이 정해져 있지 않으면 반환이 되지 않고 무한루프에 빠지게 된다
# 그러므로 재귀함수를 정의하는데 있어서 탈출조건을 구성하는 것은 매우 중요!

%%writefile test.cpp

# include <stdio.h>

void Recursive(int num)
{
    if(num <=0)
      return;
    printf("Recursive call! %d \n", num);
    Recursive(num-1);
}

int main(void)
{
    Recursive(3);
    return 0;
}

2.グラフとツリー

データ構造図の一種で、グラフィックツリーで定義されたノードと接続された直線からなり、方向性を有する非循環グラフィック方向性、無方向性はいずれも存在方向図であり、周期サイクル、非サイクルのみが存在する.1つのノードの自己循環図も1つの非循環図しか存在しないルートノードが存在しない概念がないルートノードが1つしか存在しない親-子-親-子ノードが存在しない概念がないルートノード以外のノードが1つしかない親ノードモデルネットワークモデル階層モデルDFS、BFDFS、BFDFS、BFS方式の先頭、中央、後列巡視幹線の本線の個数は自由で、N個のノードがない木は常にN-1本の幹線の例と種類地図を持っている可能性があり、最短経路、選手科目は真樹、バイナリナビゲーションツリー、バイナリhop、バランスツリー

2-1. ツリー(Tree)

定義:ツリーは階層関係を表します.

一般資料構造であれば、何かを貯蔵・取り出したものの全てであることが理解できる.スタックやキューのように、線形資料構造の焦点はここにあるからです.しかし、資料構造は根本的に何かを表現するツールである.理解ツリー理解の第1のステップ

は、表現の記憶および削除機能を提供する.

つまり、木を使って何を保存して取り出すかという考えをクリアし、木の資料構造を使う鍵だと考えています!

木の上向きと下向きの延長は重要ではありません.重要なのは、その枝が上向きに延びていることです.

2-3. 04/13地元の人の質問

589. N-ary Tree Preorder Traversal
https://leetcode.com/problems/n-ary-tree-preorder-traversal/

def preorder(node):
    if node is None:
        return 
    print(node.val)
    preorder(node.left)
    preorder(node.right)

class Solution:
    def preorder(self, root: 'Node') -> List[int]:

        nodes = [] # 파이썬은 인접행렬을 리스트로 구현
        
        def pre(root): # preorder 순회니까 
            if not root: # root 에서 시작해야함! 
                return
            nodes.append(root.val) # root node append 
            for child in root.children: # root의 children을 차례로 반복문을 돌아서 돌고
                pre(child) # children 아래의 child들을 재귀함수로 불러서 다시 돌고
        pre(root) 
        return nodes # 담긴 노드의 리스트 반환

🔥 3. N-Queens problems

1) https://leetcode.com/problems/n-queens/
return all distinct solutions to the n-queens fuzzle(Each solutionはn-queens'placementを含むdistinct board構成、where'Q'and'.'の2つはそれぞれ1つのqueenと1つの空き空間、すなわち[.Q.]を表す."...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]] 存在する答えを返す/1<=n<=924579182

2) https://leetcode.com/problems/n-queens-ii/
return the number of distinct solutions to the n-queens puzzle/1 <= n <= 9

3) https://programmers.co.kr/learn/courses/30/lessons/12952
return:nは、条件を満たす方法数/nが12以下の自然数

として構成することができる.

4) https://www.acmicpc.net/problem/9663
return:N個のクイーンズエリアへの攻撃が許可されていない場合、出力/(1≦N<15)

🔥 4.N-Queensの問題を理解し、psudo code

N*N国際碁盤は

存在する

N個のQueenが存在する.それぞれの皇后は一歩移動して、互いに攻撃することができて、これは脅威の存在です.横(row)、上下(col)、対角線(dia)に移動できます.このようなqueenがN個の脅威で互いに存在しない場合、同じ行、列、対角線に置くことはできません.

クイーンズエリアを解放できない場合は、ナビゲーションを行うことなく、直接上のノードに戻ってナビゲーション(トリミング)

を行う.
ここを見ると、2次元マトリクスを作るためにforゲートを2回回すようです!よく考えたら!!

チェス盤に皇后を置くとき、ある行に皇后が置いてあると、その行は絶対に皇后を置くことができないので、1次元arrを使うことができます!

皇后を一列に置くことはできません.同じColとDiaに置くことはできません.

承諾:同一行検査

ColとDIAも同様に行います

再度チェックすると,ノードをチェックする際に希望のある(希望のある)ノードのみが残り,希望のノードは枝切り(剪定)されず,DFSとの違いは

作成するコード

Queenの関数を配置するには(iから終了まで)

所望関数(colが同じでdiaが同じであればfalse)

🔥 5.定式化

def solution(n):
    global answer
    answer = 0

    for i in range(n):
        col = [i] + [0]*(n-1) # col 정의 colㅣ[a] = 인 경우, b행 a열에 퀸이 위치해있다는 뜻
        check(0,col)
    return answer

def check(idx,col):
    global answer
    n=len(col)
    if promising(idx,col) :
        if idx==n-1: # 현재 열이 마지막 열일 경우 모든 열이 퀸들을 만족하므로 
            answer += 1
        else :
            for j in range(n):
                col[idx+1] = j # 다음 열에 대해 0부터 n-1행까지 경우에 대해 퀸 check!
                check(idx+1,col)

def promising(idx,col):
    for k in range(idx):
        if (col[idx]==col[k]) or (abs(col[idx]-col[k])==idx-k) :# 행이 같은 경우, 대각선에 있는 경우 pruning
            return False
    return True

def check(idx,col):
    global answer
    n=len(col)
    if promising(idx,col) :
        if idx==n-1:
            answer += 1
        else :
            for j in range(n):
                col[idx+1] = j
                check(idx+1,col)


def promising(idx,col):
    for k in range(idx):
        if (col[idx]==col[k]) or (abs(col[idx]-col[k])==idx-k) :
            return False
    return True

def solution(n):
    global answer
    answer = 0

    for i in range(n):
        col = [i] + [0]*(n-1)
        check(0,col)
    return answer

# 비슷한 다른 풀이


def possible(x, y, n, col): # promising 함수
    for i in range(x):
        # 같은 열에 위치하는지 or 같은 대각선에 위치하는지 확인
        if y == col[i] or abs(y - col[i]) == x - i:
            return False
    return True

def queen(x, n, col):
    
    # row가 끝까지 갔으면 성공!
    if x == n:
        return 1
    
    count = 0
    
    for y in range(n):
        # 다음 퀸을 놓을 수 있는 경우만 진행
        if possible(x, y, n, col):
            col[x] = y # x번째 row의 col index 저장 ex) col[0] = 2 0번째 행의 2번째 col에 놓여져 있다.
            count += queen(x+1, n, col) # row index 증가 후 호출
            
    return count

def solution(n):
    
    col = [0] * n

    # 0은 세로축의 시작점 
    # n은 맵의 크기
    # col은 row 의 index를 담기 위한 리스트
    answer = queen(0, n, col)
    
    return answer

0行目からn-1行目までqueenを順番に配置します.各行に0～n-1列の皇后を設定します.このとき、現在のqueen配置の位置が有効であれば、次の行に対してdfsが呼び出され、後の追跡アルゴリズムのようにqueen idx[i]が後にリセットされる.ただし、この解法では、1次元arrayを使用すると、次のfor文を迂回して既存のqueenの位置を削除するので、リセットする必要はありません.2 Dアレイを使用している場合は、リフレッシュする必要があります.

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        queen_idx = [0 for _ in range(n)] # queen_idx[i] = x -> matrix[i][x]에 queen이 놓여있다
        answer = []

        # i-1번째 행까지 queen이 놓여있다는 가정 하에 i번째 행에 queen을 놓는다.
        def isValid(i: int) -> bool:
            for k in range(i):
                if queen_idx[k] == queen_idx[i] or abs(k-i) == abs(queen_idx[k]-queen_idx[i]): return False
            return True

        def dfs(i: int):
            if i == n:
                answer.append(list(map(lambda x: "".join(["Q" if x == idx else "." for idx in range(n)]), queen_idx)))
                return

            for j in range(n):
                queen_idx[i] = j
                if isValid(i):
                    dfs(i+1)

        dfs(0)
        return answer

参照)
https://www.geeksforgeeks.org/backtracking-introduction/
https://www.geeksforgeeks.org/n-queen-problem-backtracking-3/?ref=gcse