https://www.acicpc.net/problem/15649
15649번: N과 M (1)
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해
www.acmicpc.net
입력
1 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
- 상태공간 트리의 관점으로 보자면..
- N은 트리의 자식들이고
- M은 조사할 트리의 Depth(Level)라고도 할 수 있다,
출력
- 트리가 주어진 Depth (M) 까지 도달했다면 지나온 경로를 출력 하는것 이라고 할 수 있다.
생각방법
1. 백트래킹
용어
promising & tree & pruning & child1. promising
> 해답이 나올 가능성 없는것 - nonpromisng
> 해답 나올 가능성은 있는것 - promising 2. 그래서 backtracking 은?
> 1. DFS를 진행한다.
> 2. 노드의 유망성을 점검한후
-nonpromising 이면
부모노드로 backtraing 하고
-promisng 한 다른 자식
노드로 검색을 진행 하는것 3. 개인적으로 느낀것
보통 그래프 문제에서
현재 서있는 노드를 나타내기 위해 오직,
그래프를 이루는 컨테이너 인덱스를 접근했다
하지만, 함수자체 그리고 함수의 매개 변수로도 노드의 위치를 표시할 수 있다.
사용하는 자료구조
1차원 배열
- 출력할 경로를 담아주기
- bool형 visit 함수
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
#include <iostream>
#include <vector>
using namespace std;
int N, M;
bool visit[10]= {false, };
vector<int> outputSet;
void backtrack(int curNode, int depth)
{
if (depth == M) {
for (int K : outputSet) { cout << K << ' '; }
cout << '\n';
}
else{
for (int i = 1; i <= N; i++)
{
if (visit[i] != true) {
visit[curNode] = true; outputSet.push_back(curNode);
backtrack(i, depth+1);
visit[curNode] = false; outputSet.pop_back();
}
}
}
}
int main()
{
ios::sync_with_stdio(false); cin.tie(NULL);
cin >> N >> M;
for (int i = 1; i <= N; i++)
backtrack(i, 0);
return 0;
}
|
cs |
참고한 블로그
https://hanbi97.tistory.com/115
백트래킹 - N과 M
백트래킹 - 제약 조건을 만족하는 문제를 해결하기 위해 쓰는 알고리즘 - 특정 조건을 만족하는 조합 알고리즘에 해당하는 모든 해를 찾는 문제 모든 경우의 수 중 조건에 위배되는 경우는 빼고
hanbi97.tistory.com
'PS > 알고리즘' 카테고리의 다른 글
| [백준 1543번] 문서 검색 (c++ <string> 레퍼런스 ) (0) | 2021.07.05 |
|---|---|
| [백준 11719번] 그대로 출력하기 2 (<string> Getline 문자열 공백 허용 입력) (0) | 2021.07.05 |
| [상태공간 트리의 탐색 - 0] 목차 (0) | 2021.07.05 |
| [백준 17466번] N! mod P 모듈러 연산 성질 (0) | 2021.07.02 |
| [프로그래머스 정렬] (level1) 1번 - K번째 수 (0) | 2021.06.30 |