[15649번] 백 트래킹 - N과 M(1) with Python (★)

문제

 

참고한 코드

n, m = map(int, input().split())

s= []

def dfs():
    if len(s) == m:
        print(' '.join(map(str, s)))
        return
    for i in range(1, n+1):
        if i not in s:
            s.append(i)
            dfs()
            s.pop()
            
dfs()

> 참고한 블로그

https://jamesu.dev/posts/2020/04/13/baekjoon-problem-solving-15649/

백준 문제 풀이: 15649 - N과 M (1)

> join 함수에 관한 블로그

https://blockdmask.tistory.com/468

[python] 파이썬 join 함수 정리 및 예제 (문자열 합치기)

> 이번에 join 함수와 백트래킹에 대한 의미를 알아보았다!!!

 

내가 해석한 코드 설명

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

> n, m 은 자연수 N, M을 받을 변수입니다.

> s 변수는 값을 출력하기 위한 빈 리스트입니다.

 

def dfs():
    if len(s) == m:
        print(' '.join(map(str, s)))
        return
    for i in range(1, n+1):
        if i not in s:
            s.append(i)
            dfs()
            s.pop()

> 먼저 if문을 사용하여 s 변수의 길이가 m 변수와 같다면 ' '.join(map(str, s)) 을 추출하도록 되어있다.

> 이 의미는 s 변수는 m개의 값만큼의 길이일 때마다 값을 추출해야하기 때문이다.

> 그리고 s 변수는 리스트로서 join 함수를 사용하면 join 앞에 있는 문자열이 각 리스트의 값 사이에 들어가게 된다.

> 예제 출력을 보면 각 값은 빈 칸을 두고 출력되기 때문에 ' '.join 함수를 사용한 것이다.

> 그리고 for 문(반복문)을 range(1, n +1) 범위만큼 사용하고 dfs 를 사용하여 s 변수에 같은 값이 존재하지 않으면 s 변수에 값을 추가하고, 그와 동시에 재귀함수를 사용하여 dfs() 를 다시 적용시킨다.

> 처음에 이해가 잘가지 않았는데, 이렇게 하면 s 변수에 들어간 값을 통해 얻을 수 있는 값들은 전부 얻고 나오게 된다.

> 그리고 다시 그 값을 pop() 함수를 통해 빼주면서 반복된 값을 없게 해준다.