[백준_15663]N과M(9)

 

ttps://www.acmicpc.net/problem/15663

15663번: N과 M (9)

 

문제

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

• N개의 자연수 중에서 M개를 고른 수열

입력

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

둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.

출력

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

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

 

문제풀이

주말에 걸쳐 백트래킹에 부족함을 느껴 N과M 시리즈를 풀었다. 몇몇 문제가 풀려져 있었는데 itertools를 사용했던 것이라 백트래킹 방식으로 전부 한번 다시 되짚었다. 총 12문제로 이루어져있고 6문제씩 순열과 조합으로 구분되어 있다. 타 문제들은 범위설정만 해주면 중복 여부에 따른 조합과 순열만 구하면 되었지만 이 시리즈 중 N과M 9번에서 생각할 부분이 많았던 것 같아 우선 포스팅 하겠다. 

문제 풀이를 보기 전에 백트래킹(Backtracking)에 대해 우선 생각해보자. 백트래킹이란 해결책에 대한 후보들을 넓혀가다 가능성이 없다고 생각되는 순간에 다시 back(백트랙)하여 정답을 찾아가는 알고리즘으로써 제약 충족 문제에 유용하다. DFS와 백트래킹은 주로 같이 쓰이는데 DFS는 백트래킹의 골격을 이루는 알고리즘으로써 백트래킹은 주로 재귀로 구현한다. 최악의 경우에는 모든 경우를 다 거친 다음에 목적지에 도착할 수 있기 때문에 브루트포스와 유사하기도 하다. 하지만 가능성이 없는 경우는 즉시 되돌아가는(포기하는) 점에서 매번 같은 경로를 방문하는 브루트포스보다 훨씬 유용한 방식이다.

 

이 문제에선 box의 길이가 m이 되었을 때 리턴하는 제약을 걸었고 중복을 피하기 위해 방문처리를 나타낼 배열을 만들어 True로 방문처리를 해준후 재귀적으로 dfs함수를 위치해주었다.

더불어

* box 리스트를 바꿔주는 방식을 취하기 위해 pop과 append등을 추가로 적을 수 있겠으나 append 대신 '+' 연산자를 사용하여 새로운 배열이 만들어지게끔 하여 재귀호출이후 pop() 작업을 따로 안 해주어도 되겠다.

* 추가로 sort()는 리스트만을 위한 메소드로 리스트를 정렬된 상태로 변경하는 파괴적인 함수인 반면

sorted는 이터러블 객체로부터 정렬된 리스트 생성하는 비파괴적 내장 함수이다. 그렇기에 아래 코드에서 sorted 다음 list를 적지 않아도 된다.

n, m = map(int,input().split())
arr = sorted(list(map(int,input().split())))
pre_list =[0]*n
res = []
def dfs(box):
    if len(box) == m :
        res.append(list(box))
        return
    for i in range(n):
        if pre_list[i] == False:
            pre_list[i] = True
            dfs(box+[arr[i]])
            pre_list[i] = False
dfs([])
for i in sorted(set(map(tuple,res))):
    print(*i)