[#15659] N과 M(1)

문제

#15649 N과 M(1)
Silver4
적용 알고리즘: 백트래킹 알고리즘

---

풀이 방법

• 수열의 길이가 m개가 되면, 더이상 탐색하지 않고 그동안 저장되어있던 수열을 출력한다.

코드 흐름

1. 사전적으로 출력해야 하기 때문에 1부터 n까지 루프를 돈다. 1을 우선 배열에 넣는다.
2. dfs 함수를 호출한다.
   • 만일 현재 배열의 길이가 m 과 일치한다면 더 이상 탐색을 할 필요가 없다. 현재 배열을 출력한다.
   • 만일 현재 배열의 길이가 m 과 일치하지 않는다면 for문을 돌면서 그 다음 수를 배열에 넣는데.(이때 i와 배열에 이미 들어간 숫자 검사를 하여 중복된 숫자는 들어가지 않게 된다.)
3. 2의 과정에서 첫 번째 케이스에 해당한다면(len(arr) == m) arr.pop()코드에 도달하여 가장 마지막에 넣었던 값을 빼고, for문을 다시 돌면서 그 다음 숫자를 배열에 넣는다.
4. n까지 반복한다.

코드

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)
            dfs()
            arr.pop()


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

dfs()

체감 난이도: 4.9/5
아니 진짜 진심으로 코딩을 너무 오랜만에 했더니 와 너무 어렵다… 코딩하는법도 다까먹음 진짜 코딩을 꾸준히 해야하는거같다…