[백준 / Java] 15649번 N과 M (1)

 

사용한 알고리즘(백트래킹)

https://cobi-98.tistory.com/22

[필수 알고리즘] 재귀호출 기본 -백트래킹(Backtracking)

 

🔒 15649번 N과 M (1)

✔ 문제 설명

🚩 요구사항 분석

• 백트래킹을 이용하여 방문한 노드를 확인, 검사하기 위한 boolean 배열 생성 
• 탐색 과정에서 값을 담을 int 배열 생성

 

🔑 문제풀이

자연수 N과 M을 정의하기위해 BufferedReader 을 사용하여 StringTokenizer로 값을 전역변수 지정하였다.

 

depth를 통해 재귀가 깊어질 때마다 (DMBackTracking함수) depth를 1씩 증가시켜

M과 같아지면 더이상 재귀를 호출하지 않고 탐색과정 중 값을 담았던 arr 배열을 출력해주고 return 해준다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {

    public static int N; // 자연수 N
    public static int M; // 자연수 M

    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());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        arr = new int[M];
        visit = new boolean[N];

        NMBackTracking(0);
        System.out.println(sb);
    }

    public static void NMBackTracking(int depth){
        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 값 저장
                NMBackTracking(depth + 1); // 다음 자식 노드 방문을 위해 depth 1 증가시키면서 재귀호출
                
                // 자식노드 방문이 끝나고 돌아오면 방문노드를 방문하지 않은 상태로 변경
                visit[i] = false;
            }
        }

    }
}