[알고리즘][백준][15649] N과 M (1)

문제

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

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

입력

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

출력

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

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

예제 입력 1 복사

3 1

예제 출력 1 복사

1
2
3

예제 입력 2 복사

4 2

예제 출력 2 복사

1 2
1 3
1 4
2 1
2 3
2 4
3 1
3 2
3 4
4 1
4 2
4 3

 

풀이

백 트래킹 기본예제 문제이다. 백 트레킹이란 DFS를 사용하여 풀 수 있는데, 일반적인 DFS와의 차이점은 가지치기를 한다는 점이다.

모든 경우의 수를 탐색하는 대신 조건을 걸어서 유망(promising)하지 않은 경우에는 탐색을 중지하고 이전 노드로 돌아가서 다른 경우를 탐색한다.

 

1. 매개변수, 입력처리

import sys
input = sys.stdin.readline

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

 

• 여러줄 또는 반복문으로 입력 받는 경우에는 input()은 시간초과가 발생할 수 있다. 이럴 때, sys.stdin.readline() 을 사용
• n과 m을 입력받는다
• 방문처리를 해줄 check 배열 선언

2. 백트래킹 구현

이제 DFS 함수를 만들어 준다. DFS는 재귀함수로 반복될 것이기 때문에 함수 출력 조건을 먼저 걸어준다. 리스트 check안에 m개의 요소가 쌓인다면 출력해주도록 한다.

def back():
    if len(check) == m:
        #print(' '.join(map(str, check)))
        for i in range(m):
            print(check[i], end=" ")
        print()
        return
   
    else:
        for i in range(1,n+1):
            if i not in check:
                check.append(i)
                back()
                check.pop()

• 백트래킹의 조건으로 위에 설명한 방문했을 때는 제외 시키도록 조건문을 걸어주어 아직 방문하지 않은 경우에만 방문해 주도록 한다

 

3. 전체 코드

import sys
input = sys.stdin.readline

def back():
    if len(check) == m:
        #print(' '.join(map(str, check)))
        for i in range(m):
            print(check[i], end=" ")
        print()
        return
   
    else:
        for i in range(1,n+1):
            if i not in check:
                check.append(i)
                back()
                check.pop()

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