백준 15650번 : N과M(2)

◎백트래킹 문제

◎앞에 순열문제와 다른점 : 중복 x

 

def dfs(cnt):
    if cnt == M:
        for i in range(len(arr)):
            print(arr[i], end=' ')
        print()
        return
    for i in range(N):
        if visit[i]:
            continue
        visit[i] = True
        arr.append(num_list[i])
        dfs(cnt+1)
        arr.pop()
        #여기까진 순열과 동일
        #순열과 다른점은 밑에 코드
        #원래는 visit[i] = Flase로 짰었음
        # 근데 밑에는 i보다 하나 큰 범위부터 False를 만들어줌
        # i전의 visit은 True상태로 고정!
        #append되지 않음
       for j in range(i+1, N):
            visit[i] = False


N, M = map(int, input().split())

num_list = [i+1 for i in range(N)]
visit = [False]*N
arr = []

dfs(0)

True상태 잘 보기 현재 0번째 열완료하고 True로 설정돼있음