CT | 백준 15649번 N과 M (1)

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

 

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();

        scanner.close();

        ArrayList<Integer> a = new ArrayList<>();
        boolean[] visited = new boolean[n + 1];

        backtrack(n, m, a, visited);

    }

    public static void backtrack(int n, int m, List<Integer> sequence, boolean[] visited) {
        if (sequence.size() == m) {
            for (int num : sequence) {
                System.out.print(num + " ");
            }
            System.out.println();
            return;
        }

        for(int i = 1; i <= n; i++ ){
            if (!visited[i]) {
                visited[i] = true;
                sequence.add(i);
                backtrack(n, m, sequence, visited);
                sequence.remove(sequence.size() - 1);
                visited[i] = false;
            }
        }
    }

}

 

해당 문제는 백트래킹(Backtracking) 알고리즘을 사용하여 해결하였습니다. 

백트래킹은 모든 가능한 경우를 생성하되, 조건을 만족하지 않으면 더 이상 깊에 탐색하지 않고 돌아오는 방식입니다. 

 

backtrack 메소드에서 현재 선택한 수열의 길이가 M이라면, 이 수열을 출력합니다. 

1부터 n까지의 숫자 중에서 아직 선택하지 않은 숫자를 하나씩 추가해 나갑니다. 

선택한 숫자를 수열에 추가한 후, 다음 숫자를 선택하기 위해 재귀 호출을 합니다. 

재귀 호출이 끝나면 마지막에 추가한 숫자를 제거하여 이전 상태로 되돌립니다. 이는 다른 경우의 수를 시도할 수 있게 해줍니다.