백준 15664번: N과 M (1~12)

✔ 풀이를 위한 아이디어

• 백 트래킹 (Back Tracking)
  
  

✔ 핵심 코드

def DFS(visited, array):
    if len(array) == M:
        print(*array) #이렇게 처리하면 문자열의 요소들 사이에 공백을 포함하여 출력한다.
        return
    
    for i in range(N):
        if visited[i]:
            continue

        array.append(i+1)
        visited[i] = True
        
        DFS(visited, array)
        
        array.pop()
        visited[i] = False

• 위의 코드를 이해하는 것이 12개의 N과 M 문제를 푸는 열쇠라고 할 수 있다. 기존에 실제 스택 (Stack)을 활용하여 DFS를 구현했던 것과 달리, 백 트래킹은 재귀 함수의 호출이 스택 구조처럼 일어난다는 것을 활용한다.

• 재귀적으로 일어나는 DFS 함수의 구조를 그림으로 표현해보면 위와 같다. array의 길이가 M 값과 같아지면 해당 배열을 출력하고, 다시 자신을 호출한 곳으로 돌아가는 구조이다. 결과적으로 노란색으로 동그라미 친 곳을 보면 알 수 있듯이, 문제에서 요구한 순서대로 출력하게 된다.
• 이 코드만 제대로 이해하고 있다면, start 변수를 활용하여 오름차순으로만 출력되게 할 수도 있고, visited 배열을 없애서 같은 수가 여러번 골라지게 할 수도 있다.
  
  

✔ N과 M (10)의 해결 코드

import sys

N, M = map(int, sys.stdin.readline().split())
nums = sorted(list(map(int, sys.stdin.readline().split())))
array = []
visited = [False]*N
answers = set()

def DFS(start, array, visited):
    if len(array) == M:
        if str(array) not in answers:
            print(*array)
            answers.add(str(array))
        return

    for i in range(start, N):
        if visited[i]:
            continue

        array.append(nums[i])
        visited[i] = True

        DFS(i+1, array, visited)

        array.pop()
        visited[i] = False

DFS(0, array, visited)

• 10번 문제는 숫자를 직접 입력받고, 중복인 숫자를 허용하는 조건이 추가된다.
• 중복인 숫자를 허용하게 되면, 중복순열에 의하여 중복되는 순열들이 생기게 되므로 걸러서 출력해줘야 한다.
• 이를 위해 이미 출력된 순열들을 저장하는 집합 (Set) 을 만들고, 출력하기 전에 이미 출력된 순열인지 확인하는 과정을 거치도록 하였다. 사실 answers에 중복되게 들어갈 일은 없어서 굳이 집합으로 안만들었어도 됐을 것 같다. 리스트인 상태에서는 "not in"과 같은 연산이 안되므로 str()을 활용해 문자열로 변환하여 넣어주었다.
  
  

"경험치 복사 버그"

✔ 관련 개념

• 백 트래킹 (Back Tracking)