[백준 알고리즘] 15649번: N과 M (1)
May 05, 2020
15649번: N과 M (1)
문제
자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
입력
첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
출력
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.접근 방법:
DFS를 통해 해결하는 문제. 백트래킹을 연습하는 단계에 들어왔는데 자료구조때 배웠던 DFS를 다 까먹어서 구글링하면서 다시 공부했다. 전체적인 알고리즘은 깊이를 계속 내려가면서 방문했던 노드를 마킹하고 깊이가 내려갈 때마다 아이템을 넣을 배열 위치를 하나씩 늘려간다. 그리고 배열이 M 길이만큼 채워지면 채워진 값들을 모두 출력하고 리턴한다. 리턴된 이후에는 다시 모든 마킹을 false로 처리해주어야 다음번 경우의 수에서 값들을 정상적으로 체크할 수 있다.
통과 코드:
#include <iostream>
#include <vector>
using namespace std;
vector<bool> visited(9, false);
vector<int> numbers(9, 0);
int N, M;
void DFS(int cnt){
if (cnt == M){ // 배열에 값이 4개가 쌓이면 출력하고 종료
for (int i = 0 ; i < M ; i++){
cout << numbers[i] << " ";
}
cout << "\n";
return;
}
for (int i = 1 ; i <= N ; i++){ // 자기 자신을 제외한 다른 노드들에 방문한 적이 있는지 확인
if(!visited[i]){ // 처음 방문하는 노드를 만나면
visited[i] = true; // 방문했다고 마킹하고
numbers[cnt] = i; // 배열 0번째의 값 넣기
DFS(cnt+1); // 다음 배열에 넣을 값 찾기 재귀호출
visited[i] = false; // 여기에 왔다는건 cnt+1번째 배열에 값이 들어있는채로 리턴된거니까 다시 false로 만들어줘야 다음번 수열을 찾을 때 사용할 수 있다.
}
}
}
int main (){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> N >> M;
DFS(0);
return 0;
}
}
