[algorithm] 백준 15649 - N과 M

[algorithm] 백준 15649 - N과 M

 

안녕하세요. 심심한 코딩쟁이입니다.

 

오늘은 백준 15649번 문제 - N과 M 의 풀이를 살펴보도록 하겠습니다.

 

풀이에 사용한 언어는 Python3 입니다.

 

문제 해석과 풀이 다 함께 살펴보시죠.

 

알고리즘

---

백준 BAEKJOON 15649

 

백준 15649번 N과 M 문제 보러가기

 

문제 해석

 

이번 문제는 모든 경우를 탐색하는 백트래킹 알고리즘에 대한 문제입니다.

문제에서 N과 M이 주어지면 1에서 N 까지의 수를 이용해 M의 길이를 가진 다른 수열들을 출력하는 문제입니다.

백트래킹에서 중요한 관점은 가지치기(Pruning)입니다.

나무의 잔가지를 쳐내듯이 문제의 조건에 맞지 않는 경우는 넘어가게끔 처리하여 속도를 높이는 과정입니다.

https://namu.wiki/w/%EB%B0%B1%ED%8A%B8%EB%9E%98%ED%82%B9

백트래킹에 대한 자세한 설명은 위 링크를 참고하시기 바랍니다.

 

 

풀이

 

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

def f():
  if len(s) == m:
    print(' '.join(map(str, s)))
    return

  for i in range(1, n + 1):
    if i in s: # 가지치기
      continue
    s.append(i)
    f()
    s.pop()

f()

 

풀이 해석 및 팁

 

위 코드를 보면 가지치기 부분에 해당하는 코드에 주석을 달아두었습니다.

이 과정을 통해서 같은 숫자가 중복되는 것을 방지합니다.

한 가지 더 설명할 점은 함수를 중복적으로 호출해서 스택을 쌓는 것입니다.

함수의 작업이 모두 끝날 경우 호출되었던 상황으로 다시 돌아가게 되므로

재귀함수로 문제를 해결할 수 있습니다.

디버깅을 해보면서 각 변수에 무엇이 들어가는지 살펴보면 이해하기 쉽습니다.

---

여기까지 백준 15649번 N과 M 문제 풀이였습니다.

이번 문제의 정답률은 62% 정도입니다.

 

DFS와 백트래킹 그리고 가지치기(Pruning)에 대한 기본적인 개념을 공부해볼 수 있는 문제였습니다.

 

궁금하신 점은 댓글로 남겨주시기 바랍니다.

 

감사합니다.