[BOJ] #15649) N과 M(1) (Python, Back tracking)

🌱 문제

15649번: N과 M (1)

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

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열을 모두 출력
• 수열은 사전 순으로 증가

 

🌱 풀이 1) 파이썬 라이브러리 사용

백트랙킹 알고리즘의 대표적인 문제라고 해서 풀어본건데 문제 읽자마자 그냥 permutations 쓰면 되는 것 아님 ? ! ?

그래서 순열 뽑아주는 permutations 라이브러리 써서 제출하니까 정답,, 💙 

from itertools import permutations

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

num_list = [_ for _ in range(1, n + 1)]

for p in permutations(num_list, m):
    print(*p)

결론은 파이썬 너가 짱 (?)

 

 

🌱 풀이 2) 백트랙킹

그래도 백트랙킹 문제이니 백트랙킹을 사용해서 문제를 풀어봅시다. 백트랙킹은 현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘입니다.

N과 M(1) 문제의 상태 공간 트릴르 간략하게 나타내면 위와 같습니다.

answer = []


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


backtracking()

• 반복문을 돌면서 해당 숫자가 배열(answer)에 없다면 배열을 채웁니다.
• 그리고 backtracking() 재귀 함수를 호출합니다. 이때 backtracking() 재귀 함수는 정답을 만족시키면 return하도록 작성합니다.
• backtracking()에서 return되지 않으면 다시 반복문을 돌면서 또 answer을 채울겁니다.
• 만약 배열이 다 채워져 있으면 backtracking()에서 return이 됩니다. 그러면 answer.pop()을 통해 배열이 이전 상태로 돌아가게 됩니다.

 

🌱 정답 코드

# !/usr/bin/env python
# -*- coding: utf-8 -*-
# boj 15649 N과 M(1)

from itertools import permutations

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

# 풀이 1 (파이썬 라이브러리 사용)
num_list = [_ for _ in range(1, n + 1)]

for p in permutations(num_list, m):
    print(*p)


# 풀이 2 (백트랙킹)
answer = []


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


backtracking()