백준 알고리즘 15649 (N과 M)

수열을 출력하는 함수를 구현해야한다.
기존에 문제를 풀때 수열을 사용해본적이 있는데,
직접 구현한게 아니라

from itertools import combinations

itertools를 이용했다. 하지만 정작 수열을 만드는 문제가 나오니
당황한 나..
이번 문제를 통해 수열 구현방법을 제대로 알아가려 한다!

문제 조건 살펴보기

N과 M을 입력받고 (1~N)까지의 수를 가지고 M개를 뽑아 수열을 만드는것이다.
이때 하나의 수열에는 중복된 숫자가 포함될수 없다
ex) N=3 M=2
(1,2) 가능 (1,1) 불가능

문제 해결방법

• for문을 이용해 1~N까지 돌아야함
• 백트래킹(dfs)를 통해 방문처리하기
  -처음에 1을 방문하고, 1은 true 처리한뒤, 다음 단계에서는 1을 지나 2로 들어가기

import sys
from collections import deque
input = sys.stdin.readline

N,M = map(int,input().split())
list1 = []

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

EX) N과 M을 각각 3 과 2 가정한다
1. 처음에 list1에 1 삽입. 후 dfs가 재귀함수로 실행된다.
2. 두번째 실행된 dfs()에서는 list1에 이미 1이 들어있으므로 다음 2가 들어간후 세번째 dfs()가 실행된다.
3. 이제 길이가 같아지므로 함수는 print되고 백트래킹을 시작한다.
4. 두번째 dfs() 백트래킹해서 두번쨰 원소(2)가 pop된다. 그리고 for문이 실행되면서 2다음 3이 삽입된다.

해당 방식으로 dfs는 계속 반복될것이다.