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

문제 링크

15650번: N과 M (2) (acmicpc.net)

---

 

알고리즘 설명

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

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

---

 

문제 설명

이번 백트래킹 알고리즘 문제는 저번 알고리즘 문제와 거의 비슷하다.

N과 M을 입력받은 후, 1부터 N까지 M개의 숫자로 이루어진 조합을 찾으면 되는 문제이다.

저번과 다른점이 있다면, 저번에는 (1, 2) (2, 1) 이 서로 다른 조합으로 인정됐지만,

이번 문제에서는 같은 조합으로 취급되기 때문에 (1, 2)만 출력해야 한다는 점이다.

(문제 조건에 모든 수열은 오름차순이어야 한다고 나와있다. 따라서 (1, 2) 만 답이다.)

 

예를 들어 N = 4, M = 2 라고 할 때, 결과는

(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4) 가 나와야 한다.

 

저번 문제에서 약간의 코드만 수정하면 쉽게 풀 수 있다.

이번에도 역시 재귀함수를 이용하여 문제를 해결했다.

---

 

CODE 설명

N, M = map(int,input().split())
result = []
 
def main(num):
    for i in range(num,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(1+i)
                result.pop()
    return
 
main(1)

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

 

먼저 N과 M을 공백을 기준으로 한줄에 입력받는다.

(한줄에 여러값 입력받는 방법에 대해서 자세히 배우고 싶다면 여기 클릭)

 

그 후 재귀함수로 이루어진 main함수를 사용해 문제를 해결했다.

먼저 중복되지 않고 오름차순으로 된 조합을 구하기 위해서 함수를 다시 호출할 때 마다 

num 변수에 1을 더해 이전 숫자보다 1이 큰 값에서 반복문을 돌게 하였다.

 

처음에는 num값이 1이므로 다음에는 2부터 그 다음에는 3부터 반복문이 시작되는 것이다.

 

그러다가 result에 들어있는 값의 개수가 M이 된다면 출력 후 마지막에 있는 값을 삭제해주었다.

그렇게 반복문을 다 끝내고 함수가 종료되면, 이전 함수에서 마지막 값을 제거해줬다.

 

숫자를 통해 쉽게 예시를 들어보도록 하겠다.

N = 4, M = 2라고 할때,

처음에 num값은 1이므로 

첫번째 함수는 1부터 4까지 반복문을 돌게 된다.(N+1이 5이므로)

그 후 result에 1을 추가하고 main함수에 num+1 즉 2를 넣어 호출한다.

 

호출된 main함수는 2부터 4까지 반복문을 돌게 된다.(num+1 = 2이므로 2부터)

그리고 result에 2를 넣는데, result에 들어있는 값의 개수가 M이랑 같으므로 출력한다.

그 후 마지막 값을 제거한다. 그럼 현재 result에 들어있는 값을 1밖에 없다.

그 후 반복문을 통해 (1, 3)과 (1, 4)를 출력한다.

 

이렇게 다 출력한 후 반복문이 끝나 함수가 종료되면

이전 함수에서는 result 에 들어있는 마지막 값을 제거한다.

그럼 result에는 아무값도 없고 다시 2를 넣어서 함수를 호출한다.

 

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

말로 설명하니 약간 복잡한 감이 있는데, 재귀함수를 이미 이해하고 있다면 쉽게 풀 수 있을 것이다.

재귀 알고리즘에 대해서 잘 모른다면 아래 링크를 통해 공부해보도록 하자.

---

 

추천 글

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

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

재귀 알고리즘 공부하기.

 

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

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

백트래킹 알고리즘을 사용하는 다른 문제 풀어보기.

---

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