[python]백준 15650번: N과 M (2)

https://www.acmicpc.net/problem/15650

15650번: N과 M (2)

 

import sys
 
sys.stdin = open("input.txt",'r')
input = sys.stdin.readline
 
# 순열, 1~n까지 숫자 중에 중복없이 m개 뽑기
n, m  = map(int,input().split())
 
# 빈 배열 생성
arr =[]
 
def dfs():
    if len(arr) ==m:
        print(' '.join(map(str,arr)))
        return
 
    for i in range(1,n+1):
        if i not in arr:
            arr.append(i)
            # 마지막으로 넣은게 이전 원소보다 작으면 다시 빼기
            if len(arr) > 1 and (arr[-1] <= arr[-2]):
                arr.pop()
            else:
                dfs()
                arr.pop()
dfs()

풀이: 처음엔 for 문을 2개 작성하여 구현만 했었다. 그런 다음에 백트래킹 개념을 생각하며 풀려고 했다.
이전 문제에서 달라진 부분만 수정하기 위해 if문을 추가했다.

느낌 점: 백트래킹 문제는 처음부터 구현하지만 중간에 맞지 않은 부분을 계산할 때 바로 탈출하게 만들어야한다. 그래서 생각을 한번 더해서 안맞는 부분에 탈출하게 만들도록 만들어야 한다. 이 부분이 익숙하지 않아서 어려웠다.
내가 짠코드가 if문으로 조건을 줘서 짠 코드라 마음에 안들었다. if문이 많다는 건 억지코드다.

그래서 검색해서 올바른 풀이법을 찾아보았다.

N, M = map(int, input().split())
lst = []
 
def dfs(start):
    if len(lst) == M:  # 탈출 조건
        print(' '.join(map(str, lst)))
        return
 
    for i in range(start, N+1):
        if i not in lst:
            lst.append(i)
            dfs(i+1)
            lst.pop()
dfs(1)

1. 인수를 전부 다 넣는 것이 아니라 현재 넣는 인수값에 +1이 된 수가 다음에 들어간다.
2. 그러므로 인수값을 넣는 dfs()를 만들어서 인수값+1을 집어 넣으면 된다.
3. 처음 넣는 값은 1로 고정이다.

이러한 세 가지의 문제 해결과정과 백트래킹 개념을 그대로 구현한 풀이를 찾아 볼 수 있었다.
백트래킹 개념을 아직 잘 모르는 것 같아서 더 문제를 풀어봐야겠다.