[Baekjoon] 15650번 N과 M (2).cpp
직전에 풀어보았던 N과 M (1) 문제과 함께 백트래킹의 기초로 접하기 좋은 문제이다.
· 백트래킹(Back-tracking)
백트래킹은 쉽게 말하자면 "조건이 포함된 dfs"이다. 엄밀히 보자면 bfs나 dfs 탐색 중 특정 조건을 만족할 때 현재 탐색을 중단하고 다음 탐색을 이어가는 것인데, bfs에 백트래킹을 적용하는 것은 성능 향상에 크게 도움이 되지 않기 때문에 일반적으로 dfs를 사용할 때 같이 사용하는 기법이라고 보면 된다.
· 메인 아이디어
이번 문제의 핵심은 '중복 없이 고른 순열'이라는 것이다. 즉, {1, 2}
와 {2, 1}
은 순열을 이루는 숫자가 순서에 상관 없이 중복되므로 같은 순열이다. 이러한 순열의 특징은 간단하다. 앞의 숫자가 뒤의 숫자보다 반드시 작다.
즉, 뒤에 위치할 숫자가 앞에 위치할 숫자보다 클 때만 순열을 이룰 수 있다는 조건을 추가하면 쉽게 걸러낼 수 있다.
#include <iostream>
#include <vector>
std::vector<std::string> perms;
char nums[20];
bool visit[20];
int n, m;
void permutation(int count){
if(count == m){
std::cout << nums << "\n";
}
else {
for(int num = 1; num <= n; num++){
if(!visit[num]){
if(count > 0){ // 0 미만의 인덱스를 접근하지 않게 하기 위한 조건
if(nums[(count - 1) * 2] > num + '0'){ // 직전 원소가 현재 원소보다
continue; // 크면 탐색 종료
}
}
nums[count * 2] = num + '0';
visit[num] = 1;
permutation(count + 1);
visit[num] = 0;
}
}
}
}
int main(){
std::ios::sync_with_stdio(false);
std::cin.tie(NULL);
std::cout.tie(NULL);
std::cin >> n >> m;
for(int index = 0; index < m * 2; index++){
nums[index] = ' ';
}
permutation(0);
}
직전의 N과 M (1) 문제에서와 마찬가지로 문자열 형태로 배열을 출력하기 위해 특정 인덱스에 접근할 때 index * 2
를 해준 것 때문에 코드의 배열 인덱스에 포함된 * 2
를 혼란스러워 말자.
Author And Source
이 문제에 관하여([Baekjoon] 15650번 N과 M (2).cpp), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@cedongne/Baekjoon-15650번-N과-M-2.cpp저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)