[백준 15650번] N과 M(2)

백트래킹 유형 뽀개는 중 .. 🫠 

 

문제 링크 : https://www.acmicpc.net/problem/15650

난이도: 실버 3

15650번: N과 M (2)

 

문제

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

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
• 고른 수열은 오름차순이어야 한다.

입력

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

출력

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

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

 

---

📌 풀이 접근 방법 

백트래킹 유형만 파고있어서,, 어떤 방법으로 풀지는 알았던 문제였긴했당.. ^^

그래두 왜 백트래킹을 사용해야하는지 설명해보자면,

 

1) 문제에서 가능한 모든 경우의 수를 따져야할 때

2) 선택된 함수가 동일한 패턴을 띌 때 (재귀)

 

이 조건에 해당한다면 백트래킹을 사용해볼 수 있다.

 

이 문제는 가!능!한 모든 조합을 출력해야하기 때문에 백트래킹으로 접근할 수 있다.

 

 

 

선택된 함수가 동일한 패턴을 띈다는 것은 어떤 경우라도 일반화 시켜 재귀, 트리 형태로 나타낼 수 있다는 의미이다. 

또한 재귀에서 가장 중요한 것은 종료조건을 명확하게 설정하는 것!

 

따라서 백트래킹 코드는 두 가지 뼈대로 이루어졌다고 볼 수 있다.

1) 종료조건 -> 정답 갱신

2) 재귀(하부) 함수 호출 

 

 

나는 트리 노드의 상태(n)를 선택된 숫자의 개수로 설정하고 풀었다. 

 

선택된 숫자가 증가하면서 계속 같은 형태의 트리 모양이 호출되는 것을 확인할 수 있다. -> 재귀!

 

이렇게 구성했을 때 종료조건은 선택한 숫자 개수가 M개가 됐을 때이다.

그리고 종료시 조합에 있는 원소들(lst)을 ans 에 저장하여 정답을 갱신하면 된다.

 

재귀함수 호출시 숫자를 선택할 때 중복 방지 조건에서 자주 사용되는 visited 배열을 쓰는 것을 생각해봤는데, 

이 문제는 어차피 무조건 오름차순으로 조합을 나타내야하기 때문에 선택된 숫자보다 큰 범위 내에서만 선택하도록 for loop 의 범위를 바꿔주면 된다.

따라서 범위를 조절하는 s 값을 재귀 함수에 +1 시키는 형태로 넘겨주었다.

 

시간복잡도는 ?

최악의 경우, N = 8, M = 8이고 1부터 차례대로 숫자가 선택된다고 하면 8! 의 시간이 걸리게된다. (즉, O(N!))

따라서 완탐으로도 해결할 수 있는 문제!

 

 

📌 풀이 코드

N, M = map(int, input().split())
ans = []

# n : 선택된 원소의 개수, s: 선택할 숫자 시작점
def dfs(n, s, lst) :
    # 종료 조건
    if n == M : 
        ans.append(lst) 
        return
    
    # 재귀 호출
    for i in range(s, N+1) :
        dfs(n+1, i+1, lst + [i]) # lst에 원소를 추가하여 전달

dfs(0, 1, [])
for lst in ans :
    print(*lst)

 

 

📌 다른 풀이

이전 풀이는 멀티 트리로 구성하는 방법이고,

백트래킹에서 또 자주 사용하는 방법이 이진 트리이다. 

 

이진트리를 고려할 수 있다면 이 방법이 구현하기 훨씬 쉬운 것 같다..!

 

N의 범위는 8까지 밖에 안되니까 트리상태노드(n)을 1~N까지 숫자로 정의한다.

 

 

따라서 종료 조건은 선택된 숫자 개수(n)이 N보다 커질 때가 된다. 

그리고 정답 갱신할 때 이제까지 선택된 숫자 개수가 M개 일 때로 조건을 걸어주면 된다! 

모든 상태 노드에서 항상 조건 없이 숫자를 선택하는 경우, 선택하지 않는 경우를 고려해줄 수 있기 때문에 

두 가지 경우에 대한 함수를 재귀 호출해주면 된다. 

 

시간 복잡도는? 

N개의 숫자 각각에 대해서 2가지 경우를 고려해주기 때문에 최악의 경우, N = 8 일 때, 2^8이 된다. (즉, O(2^N))

 

 

📌 풀이 코드2

# 이진 트리로 푸는 법
N, M = map(int, input().split())
ans = []

# n : 선택할 숫자
def dfs(n, lst) : 
    # 종료 조건
    if n > N : 
        # 정답 갱신
        if len(lst) == M :
            ans.append(lst)
        return
    
    # 재귀 호출
    dfs(n+1, lst + [n]) # n을 선택했을 경우
    dfs(n+1, lst) # n을 선택하지 않았을 경우

dfs(1, [])
for lst in ans :
    print(*lst)

 

머리론 알겠는데 코드로 구현하기가 넘 어려운 백트래킹 .. 🥲 

 

 

✅ 풀이 인증