[ Baekjoon - 단계별로 풀어보기(06/19~) ] - 15단계 : 백트래킹

• 15649 : N과 M(1)

def solve(depth, N, M):
    if depth==M:
        print(' '.join(map(str,out)))
        return
    else:
        for i in range(len(visited)):
            if not visited[i]:
                visited[i]=True
                out.append(i+1)
                solve(depth+1,N,M)
                visited[i]=False
                out.pop()

N,M=map(int,input().split())
visited=[False]*N
out=[]

solve(0,N,M)

 

• 15650  : N과 M(2)

N,M=map(int,input().split())
out=[]

def solve(start):
    if len(out)==M:
        print(' '.join(map(str,out)))
        return
    for i in range(start, N+1):
        if i not in out:
            out.append(i)
            solve(i+1)
            out.pop()
solve(1)

 

• 15651  : N과 M(3)

N,M=map(int,input().split())
out=[]

def solve(start):
    if len(out)==M:
        print(' '.join(map(str,out)))
        return
    for i in range(1,N+1):
        out.append(i)
        solve(i+1)
        out.pop()
solve(1)

 

• 15652  : N과 M(4)

N,M=map(int,input().split())
out=[]

def solve(start):
    if len(out)==M:
        print(' '.join(map(str,out)))
        return
    for i in range(1,N+1):
        if len(out)>0:
            if out[len(out)-1]>i:
                continue
        out.append(i)
        solve(i+1)
        out.pop()
solve(1)

 

• 9663 : N-Queen => 꼭 Pypy3로 제출하기 (Python3은...무리에요)

import sys
N=int(sys.stdin.readline())            
row = [0] * N
res = 0   

def is_exist(x):
    for i in range(x):
        if row[x] == row[i] or abs(row[x] - row[i]) == x-i:
            return False 
    return True
 
def dfs(x):
    global res
    if x == N:
        res += 1
    else:
        for i in range(N): 
            row[x] = i
            if is_exist(x):
                dfs(x+1)
dfs(0)
print(res)

 

• 2580 : 스도쿠