15649번 - N과 M (1)
📌문제
자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
- 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
⚡입력
첫째 줄에 자연수 N과 M이 주어진다 (1 ≤ M ≤ N ≤ 8)
⚡출력
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전순으로 증가하는 순서로 출력해야 한다
코드
#include <iostream>
#define MAX 9
using namespace std;
int n, m;
int arr[MAX];
bool visited[MAX + 1];
void dfs(int depth) {
if (depth == m) { // 리프 노드까지 방문했으면 출력
for (int i = 0; i < m; i++) {
cout << arr[i] << ' ';
}
cout << '\n';
return;
}
for (int i = 1; i <= n; i++) {
if (!visited[i]) { // 방문한 노드 가지 않음
visited[i] = true; // 방문 체크
arr[depth] = i;
dfs(depth + 1);
visited[i] = false; // dfs 완료 후 방문 해제
}
}
}
int main() {
cin >> n >> m;
dfs(0);
return 0;
}
🍳풀이 방법
중복 없이 M개를 고른 수열을 출력하는 순열 문제
= 서로 다른 n개에서 r개를 순서대로 고르는 순열 (즉, nPr
)
백트래킹
으로 주로 사용하는 DFS
를 사용하여 풀었다.
처음 뻗어나가는 노드를 보면
1. 방문하지 않았으면 숫자를 배열에 추가
2. depth를 증가하여 다음 위치로 커서 이동
3. depth가 끝까지 도달한 경우 출력 및 해당 dfs 함수 종료
4. 1 ~ 3번 반복
- [depth == 0, i == 1] visited[1] = true (방문 체크). 배열에 1 추가. dfs(1) 호출
- [depth == 1, i == 1] 1번은 이미 방문한 노드. i++
- [depth == 1, i == 2] visited[2] 방문 체크 후 배열에 2 추가 dfs(2) 호출.
- dfs 호출과 i증가 반복.
- [depth == 3, i == 4] visited[4] 방문 체크 후 배열에 4 추가 dfs(4) 호출
- [depth == 4 == m] 이므로 배열에 저장된 값 출력. 리턴하므로서 dfs(4)는 종료
- [depth == 3, i == 4] n까지 갔으므로 dfs(3) 종료
- [depth == 2, i == 3] dfs(2)에서 다음 i인 3에서 다시 반복 작업
순열은 값의 중복 없이 줄 세우는 작업이다.
Author And Source
이 문제에 관하여(15649번 - N과 M (1)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@hansj05/15649번-N과-M-1저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)