Backtracking

2494 ワード

アルゴリズム#アルゴリズム# テキストリンク

Backtracking

代表例=迷路の検索

nxnの迷宮起点(0,0)到達点(n-1,n-1)

find_way(x,y):
	if x==n-1 and y==n-1:
    	return True
    if M[x][y] == safe:
    	try_down = find_way(x+1,y)
        if try_down == True:
        	return True
        try_east = find_way(x,y+1)
        return try_east
    else:
    	return False

例2=N-queens問題(8-queens問題)

4 x 4ボードで皇后を規則的に位置決めします.((0,0)~(3,3))

pseudo-code

Nqueens(k):  # x[k]를 결정 (열의 번호)
	if k >= N:
    	return
    for c in range(N):
    	if queen can place at (k,c):
        	x[k] = c
            Nqueens(k+1)

学習中...

Reference

この問題について(Backtracking), 我々は、より多くの情報をここで見つけました https://velog.io/@nine57/알고리즘-Backtracking

テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。

Collection and Share based on the CC Protocol

Get Tree Path

[コードテスト]小遣い管理