[백트래킹][BOJ] N과 M

백트래킹

• 현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘
• 임의의 집합에서 주어진 기준대로 원소의 순서를 선택하는 문제를 푸는 데 적합
• 모든 경우의 수를 탐색하는 대신 조건을 걸어서 유망(promising)하지 않은 경우에는 탐색을 중지하고 이전 노드로 돌아가서 다른 경우를 탐색
• DFS와의 차이점
  • DFS: 완전 탐색
  • 백트래킹: 아닐 때 더이상 진행하지 않음 (모든 경우를 탐색하지 않음)

def backtracking():
	if 정답:
    	정답 출력 or 저장
        return
    for 모든 자식 노드에 대해:
    	if 정답으로 선택 가능하다면:
        	자식 노드로 이동
            backtracking()
            부모노드로 이동

 

문제

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

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

입력

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

출력

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

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

 

 

풀이

1. 백트래킹

1. 문제의 조건을 만족하는 수열을 담을 리스트 arr 정의
2. 정답으로 선택 가능한지 확인하는 리스트 visited 정의
3. 백트래킹 조건
   1. 아직 방문하지 않은 경우에만 방문
   2. 방문 처리 후 arr에 값을 추가하고 backtracking 함수 호출

N, M = map(int, input().split())
arr = []
visited = [0] * (N+1)


def bt():
    if len(arr) == M:
        print(' '.join(map(str, arr)))
        return
    for i in range(1, N+1):
        if visited[i] == 0:
            visited[i] = 1
            arr.append(i)
            bt()
            arr.pop()
            visited[i] = 0

bt()

 

 

2. 순열

파이썬 순열 라이브러리를 이용한 문제 풀이

N, M = map(int, input().split())
arr = []
for i in range(1, N+1):
    arr.append(i)

a = list(permutations(arr, M))

for i in a:
    for j in i:
        print(j, end=' ')
    print()

 

 

 

 

 

 

문제:

15649번: N과 M (1)

참고 자료:

[백트래킹][실버3] 15649번 N과 M (1) - 파이썬(python)