[백준] 15649 N과 M (1) / 파이썬 (Python)

문제 링크 : https://www.acmicpc.net/problem/15649

15649번: N과 M (1)

thinking

탈출조건 > 정답 리스트와  m의 길이가 같을때 탈출하며 출력 가지치기!

반복 > 수열 출력하는 부분

방문처리 > for문의 i로 정답 리스트에 있는 지 확인 > 있으면 중복되는 경우이므로 contiue로 for문 건너뛰기

n, m = map(int, input().split()) #n, m입력
ans = [] #정답 출력 list

def n_m():
    if len(ans) == m: #재귀 탈출 조건
        print(' '.join(map(str, ans))) #list를 str로 합쳐 출력 
        return

    for i in range(1, n + 1):
        if i in ans:  # 방문(숫자가 중복) 했을 경우 for문 전체 건너뜀
            continue
        ans.append(i)
        n_m()  # 다음 자리로 넘어가기
        ans.pop() #다음을 위해서 비우기

n_m()

백트래킹인지 미친인지...

너무 어려워서 수련의 심정으로 n과 m 시리즈 격파할 예정이다.

백트래킹은 DFS과 동일하나 가지치기를 한다는 것에서 차이점이 있다.

모든 경우의 수를 탐색(완전탐색)하지 않고 조건을 걸어서 유망하지 않는 경우에는 탐색을 중지하고 이전 노드로 돌아간다.

문제 잘 읽고 1. 탈출조건 2. 반복되는 곳 3. 방문처리 잘 하기!