백준 15649 N과 M (1) [JAVA]

문제 해석

• 자연수 N과 M이 주어졌을 때 1~N까지의 자연수 중에서 중복 없이 M개를 고른 수열을 구하면 된다.

• 이 문제는 백트래킹 알고리즘을 사용하여 풀어야하는데, 백트래킹 알고리즘에 관한 설명은 POST해두었으니, 백트래킹을 처음 접한다면! 잠깐 읽고 와도 좋을 것 같다! ❗️POST : 백트래킹이란?❗️

코드

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

public class Main {

    static int N; // N
    static int M; // M
    static int[] list; //해당 순열을 저장하는 배열
    static boolean[] check; //방문여부 체크하는 배열

    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()); //N
        M = Integer.parseInt(st.nextToken()); //M

        list = new int[M]; //M개의 숫자의 순열 저장하는 배열 초기회
        check = new boolean[N]; //방문 체크하는 배열 초기화

        backTracking(0);
        br.close();
        System.out.println(sb);
    }

    static void backTracking(int row) {
        if (row == M) { //순열의 크기가 M일 경우(M개의 숫자 순열을 고르는 거기때문에 이때 종료
            for(int value : list){
                sb.append(value + " "); //순열 차례대로 배열에서 꺼내서 StringBuilder에 추가
            }
            sb.append("\n");
            return;
        }

        for (int i = 0; i < N; i++) {
            if (check[i] == false) {
                check[i] = true; //자식노드 방문할때 자기자신을 빼야하므로 true처리
                list[row] = i+1; //1부터 N까지의 숫자가 들어가기 때문에 i는 0부터 시작하므로 i+1을 넣어준다.
                backTracking(row+1); //자식노드 방문
                check[i] = false; //자식노드 모두 방문했으면 부모노드 다시 방문기록지움
            }
        }
    }
}

        

결과

느낀 점

• 백트래킹 문제는 처음 접해보는 거라 조금 헤맸지만 그래도 생각보다는 괜찮았다. (다시 복습해봐야할 문제)