[알고리즘] 백준 15654 파이썬 - N과 M(5) (백트래킹)

 

15654번: N과 M (5)

 

문제

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

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

 

문제풀이

n,m = map(int,input().split())
a=list(map(int,input().split()))
a.sort()
ans=[]
def dfs():
	#01
    if(len(ans)==m):
        print(*ans)
        return
    
    for i in a:
        if i not in ans: #02
            ans.append(i)
            dfs() #03
            ans.pop()
dfs()

- 초기 입력값들은 각각 n,m,a에 저장한 후 a를 오름차순으로 정렬한다.

- #01 : 만약 ans의 길이가 m가 같다면 ans를 공백을 기준으로 한 줄에 출력하고 return한다.

           사실상 처음 ans의 길이는 0이기에 바로 실행되는 if문은 아니다.

- #02 : 만약 ans에 i가 없다면 추가를 해준다.

- #03 : dfs()함수를 호출하여, ans의 길이가 m이 될 때까지 ans를 채워준다.

           다 채워졌다면 #01의 if문을 통해 출력을 하고 return으로 다시 돌아와 ans.pop()을 통해

           리스트의 마지막 값을 제거하고 새로운 값으로 채워넣는 과정을 반복한다. 

 

예시)

3 1
4 5 2

n,m= 3,1
a=[2,4,5]
ans=[] -> [2] -> if문 만족 후 출력 후 pop으로 값 제거 ->[] -> [4] -> if문 만족 후 전 과정 반복

 

 

 

백트래킹

[알고리즘/Algorithm] 개념: 백트래킹이란? - Kyun2da Blog

- 해당 문제는 백트래킹 문제로, 15649,15650,15651,15652,15653,15654,15655,15656,15657 등이

  비슷한 풀이방법을 사용하여 문제를 푼다.

 

 - 백트래킹은 DFS와 비슷한 개념이지만 조금 다르다. (DFS은 아래 링크를 참조)

[알고리즘] 백준 2606 파이썬 - 바이러스(DFS 풀이)

- DFS의 경우는 가능한 모든 경로를 탐색하기에, 시간 복잡도가 커지게 된다.

- 하지만 백트래킹의 경우는 그 경로가 문제 풀이가 관련이 없다면 그 경로를 가지 않는다.

  즉 모든 경우의 수 중에서 특별한 조건을 만족하는 경우만 찾아보는 풀이를 말한다.