[Baekjoon]백준 15649 N과 M (1)(실버 3) - Python, C++

문제설명

예제

문제를 읽어보면 N, M을 입력받아 길이가 M인 수열을 모두 출력하는 문제이다

python에는 permutations라는 좋은 함수가 존재하기 때문에 간단하게 이 문제를 풀면 아래의 코드가 나온다

from itertools import permutations

num, length = map(int, input().split())
sequences = list(permutations(range(1, num + 1), length))

for i in range(len(sequences)):
    print(*sequences[i])

하지만 이 문제는 백트래킹 단계에 존재하는 문제이고, 백트래킹을 배우기 위해 푸는 문제이므로

문제의 의도에 맞게 코드를 다시 작성하였다

 

함수를 재귀적으로 호출하여 문제를 해결하였는데, 먼저 현재 수열을 인자로 받아온다

현재 수열이 목표로 하는 길이와 동일하다면 바로 return 해주면 되고 아니라면 for문을 통해 현재 수열에 없는 수를

append()를 통해 집어넣는다 후에 다시 백트래킹 함수를 호출하고, 마지막 수를 pop()을 통해 원래 상태로 복구한다

원래 상태로 복구한다는 것은 다른 수를 넣는 경우에 해당한다

def generate_sequences(num, length):
    result = []
    def backtrack(curr_seq):
        if len(curr_seq) == length:
            result.append(curr_seq.copy())
            return
        for i in range(1, num+1):
            if i not in curr_seq:
                curr_seq.append(i)
                backtrack(curr_seq)
                curr_seq.pop()

    backtrack([])
    return result

num, length = map(int, input().split())
sequences = generate_sequences(num, length)
for i in range(len(sequences)):
    print(*sequences[i])

이해하기 쉽도록 예시를 들어보자면, 1이 cur_seq에 존재한다고 가정하자 (num은 4, length가 2라고 가정)

그 상태에서 backtrack 함수에 들어오면 lenght와 cur_seq의 길이가 다르기 때문에 첫번째 if문을 통과하게 될것이고

for문에 들어가게된다 이후에 for문안에 존재하는 if문에 의해 i로 2가 선택될 것이다

이후에 [1, 2] 라는 결과를 재귀적으로 호출하게 되고(1, 2는 길이가 2이므로 return이 일어남) pop()을 통해

2를 삭제하여 2 대신 3, 4와 같은 다른 수가 result에 저장이 될 것이다

그리고 이러한 과정을 반복하여 [1, 2], [1, 3], [1, 4], [2, 1], [2, 3]...처럼 계속해서 result에 저장된다

result 리스트를 for문을 통해 출력해주면 해결이다

위의 코드는 백트래킹, 아래 코드는 permutations를 사용하여 작성한 코드 제출 결과이다

---

(2025/02/21 추가)

C++로도 복습을 위하여 코드를 작성해보았다

오랜만에 다시 백트래킹을 살펴보니 너무 헷갈려서 이전에 작성한 파이썬 코드를 보고 다시 감을 잡을 수 있었다

C++에서는 다른 방식으로 방문 확인을 하였는데, visit[]배열을 만들어서 방문한 곳인지 확인하도록 코드를

작성하였다 방문하지 않은 경우에만 탐색을 하게 되며 해당 값을 사용한 경우 다시 false로 변환하여

나중에 다시 사용할 수 있도록 작성하였다

#include <iostream>
using namespace std;
int n, m;
int arr[9];
bool visit[9];

void sol(int idx) {
    if(idx == m) {
        for(int i = 0; i < m; i++) {
            cout << arr[i] << " ";
        }
        cout << "\n";
    } else {
        for(int i = 1; i <= n; i++) {
            if(!visit[i]) {
                visit[i] = true;
                arr[idx] = i;
                sol(idx + 1);
                visit[i] = false;
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >> n >> m;
    sol(0);
    
    return 0;
}

cout << endl;을 사용하면 시간 초과가 발생하므로 cout << "\n"을 활용해야할 듯 하다

앞으로도 예전에 풀었던 문제에 대하여 복습을 진행하여야할 것 같다 기억이 안 난다...ㅜ