[백트래킹 알고리즘] #1 백준 N과 M (1) (파이썬,15649번)

문제 링크

15649번: N과 M (1) (acmicpc.net)

---

 

알고리즘 설명

2024.06.02 - [[알고리즘]/[알고리즘 공부]] - [알고리즘 공부] #2 백트래킹(BackTracking) 알고리즘 with Python

[알고리즘 공부] #2 백트래킹(BackTracking) 알고리즘 with Python

---

 

문제 설명

먼저 백트래킹 알고리즘은 기본적으로 탐색할 수 없을 때 까지 탐색한 후, 더 이상 탐색하지 못 할 경우 이전 단계로 돌아가는 알고리즘을 말한다.
따라서 브루트포스 알고리즘처럼 모든 경우의 수를 탐색해야 한다는 단점이 있다.

 

먼저 1부터 N까지 중복되지 않는 M개의 숫자로 이루어진 조합을 찾는 문제로 이해할 수 있다.

이러한 문제는 재귀함수를 이용하여 풀 수 있다.

이 문제를 백트리킹과 재귀를 이용해 풀기 위해서는 숫자를 하나씩 중복되지 않게 추가한 후 만약에 숫자의 개수가 M이라면 저장을 한 후 return 해주는 방식으로 풀 수 있다.

 

자세한 설명은 코드를 보면서 하도록 하자.

---

 

CODE 설명

N, M = map(int,input().split())
result = []
 
def main():
    for i in range(1,N+1):
        if len(result) != M and i not in result:
            result.append(i)
            if len(result) == M:
                print(' '.join(map(str,result)))
                result.pop()
            else:
                main()
                result.pop()
    return
 
main()

위 코드는 문제의 정답이다.

 

먼저 N과 M을 한줄에 입력받는 것을 알 수 있다.

그 후 메인함수를 통해 문제를 해결하는데 이 함수는 재귀함수이다.

 

먼저 1부터 N+1까지 반복을 하면서 result에 숫자를 하나씩 추가한다.

result의 들어있는 숫자의 개수가 M이 아니라면 다시한번 main함수를 호출한다.

 

이 과정을 반복하면서 만약에 숫자의 개수가 M이 된다면, 현재 result의 있는 값을 출력한 후

맨 마지막에 추가된 값을 제거한다. 반복을 다 돌게 되면 return하게 된다.

 

return을 받은 함수는 한번더 마지막 값을 제거한 후 다시 값을 추가한다.

 

숫자를 통해 예시를 들면

만약에 N이 4고 M이 2라고 했을때,

 

처음에 result에는 1이 추가되고 다시 main함수를 호출한다.

호출된 main함수에서는 1을 넣으려고 하지만 이미 result에 있기 때문에 생략되고, 2를 넣게 된다.

그러면 result에는 1과 2 두개 즉 M개랑 개수가 같기 때문에 '1 2'를 출력한 후 마지막 값을 제거한다.

그 후 '1 3'을 출력, '1 4'를 출력한 후 반복을 다 돌았기 때문에 return하게 된다.

 

그럼 pop을 두번하기 때문에 result에는 아무런 값도 들어있지 않고 다시 2부터 추가된다.

 

이런식으로 반복하여 중복되지 않는 모든 조합을 찾을 수 있게 되는 것이다.

---

 

추천 글

[알고리즘 공부] #3 재귀(Recursive) 알고리즘 with Python

[알고리즘 공부] #3 재귀(Recursive) 알고리즘 with Python

재귀 알고리즘 배우기

 

[알고리즘 공부] #1 완전 탐색, 브루트포스(Brute Force) 알고리즘 with Python

[알고리즘 공부] #1 완전 탐색, 브루트포스(Brute Force) 알고리즘 with Python

브루트포스 알고리즘 배우기

---

방문해주셔서 감사합니다!