[python]백준 15649번: N과 M (1)

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

15649번: N과 M (1)

 

import sys
#sys.stdin = open("input.txt",'r')
input = sys.stdin.readline
 
n,m = map(int,input().split())
 
# 빈 배열 선언
arr = []
 
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()
dfs()

 

풀이: 백트래킹 문제는 나에게는 생소한 문제였다. dfs와 bfs 문제는 많이 풀어보았지만, 죄다 완탐의 개념이였다. 그러나 백트래킹은 달랐다. 가지치기와 효율을 따지는 문제이기 때문이다. 중간에 자신이 원하는 값이 아닐 경우 그 이후에 값들이 전혀 쓸모가 없기 때문에 바로 빠져나와야 한다. 그리고 차례대로 원소를 대입해나가야한다.
이렇게 내가 풀어왔던 방식과 많이 달랐기 때문에 매우 어려운 문제였다.

이 문제의 경우 n, m이 3, 2로 주어진다면  1,2,3중에서 2개의 중복되지 않은 수를 뽑아야 한다. 그렇다면 [1,2],[1,3],[2,1],[2,3],[3,1],[3,2]가 될 것이다.

 

이렇게 정답이 생각난다면 어떻게 구현하면 좋을까?
그 과정을 차례대로 생각해보자. []->[1]->[1,2]->[1]->[1,3]->[]->[2]->[2,1]->[2]->[2,3]->[]->[3]->[3,1]->[3]->[3,2]->[]
이렇게 되는 게  제일 쉽게 떠올리기 쉬울 것이다.

그렇다면 어떠한 과정을 해야할까?
1. 빈리스트를 생성
2. for문을 써서 1,2,3을 추가하도록 해야 함
3. for문 속에서 원소가 중복되는지 검사함
4. 중복이 되지 않는다면 추가하고 재귀를 써서 for문이 차례대로 돌도록 만듦
5. m개 원소를 가진 리스트가 만들어진다면 함수를 끝내고 마지막 원소를 빼버린다.
6. 한 사이클을 돌게되면 다시 빈리스가 되어야 하기 때문에 for문 안에 append와 pop이 둘 다 있어야 한다.

이렇게 과정을 정리하고 나서 코드로 옮기면 된다.