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

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

 

입력

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

 

문제를 풀기에 앞서, 백트래킹이란 무엇일까?

 

백트래킹은 DFS와 유사하다고 말할 수 있다. 또한 사람이 사는 사고와 유사하다고 말할 수 있다. 

경우의 수를 탐색할 때 어떤 경우의 수가 안되는게 뻔히 보이면 탐색을 안한다. -> 다른걸 탐색한다. 

 

트리, 스토쿠 등이 이에 해당하는데, 

단점은 시간 복잡도 계산이 어렵다는 것이다. 

 

이런 문제는 어떻게 풀어야 하나...

 

https://st-lab.tistory.com/114

[백준] 15649번 : N과 M (1) - JAVA [자바]

문제에서 N과 M이 주어지고, 중복되는 수를 제외한 모든 경우의 수를 탐색하면 된다. 그럼 기본적으로 재귀를 통해 풀어볼 수가 있겠다.'

 

아주.. 난이도 있는 문제다 나에게는 ,,

일단 외우고 생각하자. 

import java.util.*;
import java.io.*;

public class Main{
    
    public static int[] arr;
    public static boolean[] visit;
    public static StringBuilder sb= new StringBuilder();
    
    
    public static void main(String args[]) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        
        arr = new int[m];
        visit = new boolean[n];
        dfs(n,m,0);
        System.out.println(sb);
        
    }
    
    public static void dfs(int n,int m,int depth){
    // 재귀 깊이가 M과 같아지면 탐색과정에서 담았던 배열을 출력
        if(depth == m){
            for(int val:arr){
                sb.append(val).append(' ');
            }
            sb.append('\n');
            return;
        }
        for(int i=0;i<n;i++){
        	// 만약 해당 노드(값)을 방문하지 않았다면?
            if(!visit[i]){
                visit[i]=true;		// 해당 노드를 방문상태로 변경
                arr[depth]=i+1;		// 해당 깊이를 index로 하여 i + 1 값 저장
                dfs(n,m,depth+1);	// 다음 자식 노드 방문을 위해 depth 1 증가시키면서 재귀호출
                
                // 자식노드 방문이 끝나고 돌아오면 방문노드를 방문하지 않은 상태로 변경
                visit[i]=false;
            }
        }
    }
}

 

구조 분석

n과 m 입력받아서, 

1. 배열

2. visit (boolean)

3. StringBuilder

이렇게 3가지를 전역변수로 선언합니다. 

 

---

if( depth == m) //m까지 차면 그만해야죠, depth와 m이 같아지면 그만합니다. 

for(int val : arr){ //앞에 for을 붙이고 int 붙인다는거

 

한줄 끝나면 엔터 쳐야죠 

sb.append('\n');

retuen; // 다시 돌아간다.

---

for문{ 

    arr[depth] = i+1; //arr[]에 값넣어줘야지