[BAEKJOON/Python3] 백준 15652 N과 M(4)

www.acmicpc.net/problem/15652

15652번: N과 M (4)

＊링크로 접속하여 문제를 확인할 수 있습니다.

 

N과 M이 주어졌을 때 1부터 N까지의 자연수 중에서 M개의 수를 골라 수열을 출력하는 문제입니다. (4)이기 때문에 비슷한 문제들이 많은데 이 문제에서는 "같은 수를 여러 번 골라도 되는 것"과 "고른 수열은 비내림차순인 것" 이 두가지 특징이 있습니다. N과 M 문제들은 모두 백트랙킹을 이용하여 해결하는 문제입니다.

 

*백트랙킹(Backtracking Algorithm)은 순차적으로 해를 찾다가 해가 아닌 것 같으면 되돌아가서 해를 찾는 방법이라고 할 수 있습니다. 백트랙킹은 문제를 해결하며 해가 될 수 없는 부분은 아예 시도조차 하지 않는 것이라고 생각하면 되겠습니다. 대표적으로 미로탈출, N-queens 문제 등이 있습니다.

 

코드

 

우선 모든 수열을 구하기 위한 getAll 함수를 정의하였습니다. N과 M은 전역변수로 이용할 것이며 이 함수가 매개변수로 받는 count와 index는 각각 현재까지 수열에 담은 개수와 탐색중인 index라고 생각하면 됩니다. 함수 정의 부분이 아닌 main 부분을 보면 N과 M을 각각 정수형으로 입력 받았으며 ans라는 빈 리스트를 생성했습니다. ans 리스트에는 그때그때 정답 수열을 담을 것입니다. 또한 count와 index는 처음에 모두 0으로 시작하므로 0,0으로 getAll 함수를 호출해주었습니다.

 

getAll 함수에 대한 설명:

count는 현재까지 수열에 담은 개수를 나타낸다고 하였기 때문에 count가 M이 되면 한개의 수열이 또 구해진 것이라고 이해할 수 있습니다. 따라서 count가 M이라면 현재까지 정답을 담고 있는 리스트의 요소들을 문자열로 변환하여 공백으로 이어 출력해주고 종료합니다.

그리고 for문에서는 현재의 index부터 N까지 순환할 것입니다.

우선 index는 0부터 N-1까지, 우리가 원하는 수들은 1부터 N까지라는 것을 기억해야 합니다. ans 리스트에 i+1을 넣고 getAll 함수를 count에 1을 더하여 호출해줍니다.(index에는 1을 더하지 않는 이유는 같은 수를 여러 번 골라도 된다는 이 문제의 조건 때문입니다. 만약 같은 수를 고르면 안된다면 index에 1을 더하는 것이 좋은 방법이 될 것 같습니다.) 이 부분에서 getAll 함수를 재귀적으로 호출하여 count가 M을 도달할 때까지 진행된 후 끝나면 이 위치로 돌아올 것입니다. (순차적으로 찾게 되는 것) 재귀적으로 모두 호출하여 count가 M이 될 때까지 이 값으로 찾을 수 있는 모든 수열들을 찾았다면 다시 이 부분으로 돌아올 것이며 그러면 ans에 넣었던 값을 바로 pop해주면 됩니다.

 

 

백트랙킹은 개인적으로 조금 까다롭고 어려운 알고리즘이라고 생각하여 더욱 더 꼼꼼하게 공부해야겠습니다.