[백준] 15649 : N과M(1) [순열] - Python

N과 M(1)

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

import sys
sys.stdin = open("input.text", "rt")

n,m = map(int, input().split())
#중복없이 m개 선택 : 순열
res = []
ch = [0] * (n+1)
def DFS(L):
    if L == m: #모두 선택. 종료조건
        for x in res:
            print(x, end = " ")
        print()
    else:
        for i in range(1,n+1):
            if ch[i] == 0:
                ch[i] = 1
                res.append(i)
                DFS(L + 1)
                ch[i] = 0
                res.pop()  # 백트랙킹 시 원상복구


DFS(0)

😀 코멘트

해당 문제는 N개의 수 중 M개를 중복없이 나열.

• 즉 순열을 구하는 것.

itertools.permutations()를 쓸 수 있지만 백트랙킹으로 연습해놔야 함.

• 다시풀어봄

import sys
sys.stdin = open("input.text", "rt")
from collections import deque

n,m = map(int, input().split())
visited = [0] * (n+1)
res = []
def dfs(L):
    if L == m: # m개 뽑음. 종료조건
        print(*res)
    else:
        for i in range(1,n+1):
            if visited[i] == 0:
                visited[i] = 1 # 방문처리 후
                res.append(i)
                dfs(L+1)
                res.pop()
                visited[i] = 0 # 백트랙킹 시 원상복구

dfs(0)

• 중요한건 종료조건 ! -> m개를 뽑을 때가 종료조건!!!
  또한 순열은 처음부터 돌면서 안 뽑은 걸 추가하면 되는거야.
• 백트랙킹 시 원상복구 잊지말자.