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

[문제 링크]

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

---

문제 설명

자연수 N과 M이 주어졌을 때, '1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열'을 모두 구하는 프로그램을 작성하시오

 

입력

• 자연수 N과 M(1 <= M <= N <=8)

출력

• 사전 순으로 증가하는 순서로 수열 출력

입출력 예시

입력예시	출력예시
3 1	1 2 3
4 2	1 2 1 3 1 4 2 1 2 3 2 4 3 1 3 2 3 4 4 1 4 2 4 3

 

 

 

 

문제 풀이

• DFS를 사용해서 백트래킹 풀이
• 재귀 호출을 통해서 1 ~ n까지 돌면서 중복없이 m개의 수를 탐색한다.
• 종료 조건 : count가 m과 같으면 해당 수열을 출력하고 재귀 호출 종료

(1) ArrayList 사용(나의 풀이)

ArrayList의 contains() 함수를 사용해서 중복체크를 하고, 재귀가 종료되면 ArrayList에 마지막에 담긴 수를 제거한다.

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

public class Main {

    public static int n, m;
    public static ArrayList<Integer> aList = new ArrayList<>();

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

        dfs(0);
    }

    public static void dfs(int count) {
        //종료조건 : if count == m 이면 재귀 종료
        if (count == m) {
            for (Integer integer : aList) {
                System.out.print(integer + " ");
            }
            System.out.println();
            return;
        }

        //재귀 호출
        for (int i = 1; i <= n; i++) {
            //수열에 중복되는 수가 없을 경우 해당 수를 aList에 넣고 재귀호출
            if (!aList.contains(i)) {
                aList.add(i);
                dfs(count + 1);
                aList.remove(count);	//재귀가 끝나면 arrayList에서 마지막 숫자를 제거한다.
            }
        }
    }
}

 

 

 

(2) array, visited 배열 사용

boolean 타입인 visited 배열을 사용해서 중복체크를 하고, 재귀가 종료되면 visited 배열을 false

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

public class Main {

    public static int n, m;
    public static boolean[] visited = new boolean[10];
    public static int[] array;

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

        array = new int[m];
        dfs(0);
    }

    public static void dfs(int count) {
        //종료조건 : if count == m 이면 재귀 종료
        if (count == m) {
            for (int i : array) {
                System.out.print(i + " ");
            }
            System.out.println();
            return;
        }

        //재귀 호출
        for (int i = 1; i <= n; i++) {
            if (!visited[i]) {
                visited[i] = true;  //사용한 숫자 방문 처리
                array[count] = i;
                dfs(count + 1);
                visited[i] = false;
            }
        }
    }
}