アルゴリズムマラソン6日目

7703 ワード

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

35日です。

NとM(2)
まず、この問題をよりよく理解するためには、まず次の問題を解決したほうがいい.
NとM(1)

n, m = list(map(int, input().split()))
s = [] # m개의 수열을 저장하기 위한 리스트

def dfs():
    if len(s) == m: # 수열이 m개가 되면 모든 숫자를 출력하고 리턴
        print(' '.join(map(str, s)))
        return

    for i in range(1, n + 1): # 1부터 n까지의 숫자들을 모두 확인
        if i not in s: # 중복이 아닐 경우에만 숫자 넣기
            s.append(i)
            dfs()
            s.pop()

dfs()

ここでn=4,m=2であれば、i=1からs=[1]→再帰→s=[1,2]→出力→pop→s=[1]→再帰→出力→pop→s=[1,3]→s=[1]→再帰→出力→pop→i=2のときである.このように行います.
NおよびM(2)の問題において、s=[1,4]、[1,2]が繰り返される場合、[2,1]のみが出力されるべきである.
再帰呼び出し時に、自分の次の数字を呼び出すことで、前の数字が後の数字より小さい場合を排除します.

n, m = list(map(int, input().split()))
s = []

def dfs(start):
    if len(s) == m:
        print(' '.join(map(str, s)))
        return

    for i in range(start, n + 1):
        if i not in s:
            s.append(i)
            dfs(i + 1) # 재귀 호출 시에는 자기 다음 숫자를 불러오게 된다.
            s.pop()


dfs(1)

36番

N-Queen
N × Nチェス盤にN個の皇后があり、皇后同士が攻撃できない場合は、数字を出力すればよい.
相手が攻撃できないようにするには、女王の直線や対角線に他の皇后が置かれているかどうかをチェックします.
遡及に関する問題がずっと出ているので、遡及に関する概念を整理してみましょう.
バックトラッキングとはDFS+枝切りです.DFSは再帰的に問題を解決することを意味し、ブランチはbreakやcontinueなどを中間的に使用して不要な再帰呼び出しを阻止することを意味する.
難しすぎます...