BOJ_BackTracking_15649_N과 M (Java)

문제 풀이에 대한 오류 지적 및 개선 방향 제시는 항상 환영합니다.
알고리즘 문제를 엄청 잘 풀고 막 문제 보자마자 아 이거네 쉽네 ㅎㅎ 이렇게 푸는 입장이 아니라서
그 어떤 문제에 대한 비판 지적 방향 제시는 언제나 감사하게 받겠습니다. 

이 문제가 올라가는 저장소 : https://github.com/hwk0911/Junit-TDD

hwk0911/Junit-TDD

 

15649번 - N과 M (1) 성공

 

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	512 MB	13052	7952	5433	61.293%

문제

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

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

입력

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

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안 되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

제한

 

예제 입력 1

3 1

예제 출력 1

1
2
3

예제 입력 2

4 2

예제 출력 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

예제 입력 3

4 4

예제 출력 3

1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 1 3
2 4 3 1
3 1 2 4
3 1 4 2
3 2 1 4
3 2 4 1
3 4 1 2
3 4 2 1
4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1

힌트

 

출처

• 문제를 만든 사람: baekjoon

<Main.java>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        ArrayList<String> data = new ArrayList<>();

        String[] temp = br.readLine().split(" ");
        int N = Integer.parseInt(temp[0]);
        int M = Integer.parseInt(temp[1]);

        for (Integer index = 1; index < N + 1; ++index)
        {
            data.add(index.toString());
        }

        boolean[] visited = new boolean[data.size()];

        recursion(visited, M, 0, data, "");
    }

    public static void recursion(boolean[] visited, int M, int count, ArrayList<String> data, String sequence)
    {
    	//termination check
        if (M == count)
        {
            System.out.println(sequence);
            return;
        }

		//recurse next
        for (int index = 0, size = data.size(); index < size; ++index)
        {
            if (!visited[index])
            {
                visited[index] = !visited[index];
                recursion(visited, M, count + 1, data, sequence + data.get(index) + " ");
                visited[index] = !visited[index];
            }
        }
    }
}

 

백트래킹의 기본을 연습할 수 있는 좋은 문제다.

1. main
   1. 데이터를 입력받을 ArrayList 선언
   2. N, M 입력받아 초기화
   3. 1 이상 N 이하 데이터 ArrayList에 저장
   4. 방문 확인을 위한 ArrayList와 사이즈가 같은 boolean배열 visited선언
2. recursion
   1. 매개 변수 : 방문 확인, 입력받은 M, 사용한 데이터 수 (수열의 길이), 데이터, 만들어진 수열
   2. termination check (종료 확인)
      1. M과 count가 같을 때 종료 (수열의 길이와 만들어진 수열의 길이가 같을 때)
      2. for ( index = 0 -> data.size )
      3. visited를 통해 확인, 기본값이 false이므로, false인 경우 실행문 실행
      4. visited [index] 반전
      5. 재귀 함수를 통하여 다음 문법 실행
         1. 매개 변수 변화 : count + 1, sequence + data.get(index) + " "
         2. 재귀 빠져나온 뒤, visited 다시 반전
      6. 전체 재귀 반복