[백준 15649번] 백트래킹 N과 M(1)

 

https://www.acicpc.net/problem/15649

15649번: N과 M (1)

입력

1 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

• 상태공간 트리의 관점으로 보자면..
  • N은 트리의 자식들이고
  • M은 조사할 트리의 Depth(Level)라고도 할 수 있다,

---

출력

1. 트리가 주어진 Depth (M) 까지 도달했다면 지나온 경로를 출력 하는것 이라고 할 수 있다.

---

생각방법

1. 백트래킹

용어

promising & tree & pruning & child

1. promising

> 해답이 나올 가능성 없는것 - nonpromisng
> 해답 나올 가능성은 있는것 - promising 

2. 그래서 backtracking 은?

> 1. DFS를 진행한다.

> 2. 노드의 유망성을 점검한후
    -nonpromising 이면 
    부모노드로 backtraing 하고

    -promisng 한 다른 자식 
    노드로 검색을 진행 하는것  

3. 개인적으로 느낀것

보통 그래프 문제에서 
현재 서있는 노드를 나타내기 위해 오직,
그래프를 이루는 컨테이너 인덱스를 접근했다

하지만, 함수자체 그리고 함수의 매개 변수로도 노드의 위치를 표시할 수 있다.

---

사용하는 자료구조

1차원 배열

1. 출력할 경로를 담아주기
2. 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; }   Colored by Color Scripter

cs

참고한 블로그

https://hanbi97.tistory.com/115

백트래킹 - N과 M