백준 15649번 자바 문제 답/해설(N과 M (1) 문제)

[1] 백준 카테고리
단계별로 풀어보기
백트래킹

1단계 N과 M (1)

[2] 문제
자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

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

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

3. 예제 입력 1
3 1

4. 예제 출력 1
1

2

3

 

5. 예제 입력 2

4 2

 

6. 예제 출력 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] 정답
1. 정답 해설 미포함

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

public class Main {
	public static int[] arr;
	public static boolean[] check;
	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());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());

		arr = new int[M];
		check = new boolean[N];
		btm(N, M, 0);
		System.out.println(sb);
	}

	public static void btm(int N, int M, 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 (!check[i]) {
				check[i] = true;
				arr[depth] = i + 1;
				btm(N, M, depth + 1);
				check[i] = false;
			}
		}
	}
}

2.정답 해설 포함

import java.io.BufferedReader;
/* BufferedReader 사용을 위해서 java.io.BufferedReader 클래스를 import 한다.
Enter를 경계로 인식하고 받은 데이터는 String으로 고정된다.*/
import java.io.InputStreamReader;
/* byte 단위 데이터를 문자 단위 데이터로 처리할 수 있도록 변환해주기 위해서
InputStreamReader를 사용한다.
InputStreamReader 사용을 위해서 java.io.InputStreamReader 클래스를 import 한다.*/
import java.io.IOException;
/* 예외 처리를 위해서 IOException를 사용한다.
IOException 사용을 위해서 java.io.IOException 클래스를 import 한다.*/
import java.util.StringTokenizer;
/* 공백 단위로 호출하기 위해서 StringTokenizer를 사용한다
StringTokenizer를 사용하기 위해서
StringTokenizer java.util.String 클래스를 import 한다.*/

public class Main {
// 접근제어자 public으로 Main class를 선언한다.
	public static int[] arr;
	// 접근제어자 public으로 메모리에 상주하게 int형 배열 arr를 선언
	public static boolean[] check;
	// 접근제어자 public으로 메모리에 상주하게 boolean형 배열 check를 선언
	public static StringBuilder sb = new StringBuilder();
	// 접근제어자 public으로 메모리에 상주하게 StringBuilder 객체 sb 선언

	public static void main(String[] args) throws IOException {
	// 접근 제어자 public으로 메모리에 상주하게 main 함수 선언
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		// BufferedReader 객체 br 선언
		StringTokenizer st = new StringTokenizer(br.readLine());
		// StringTokenizer 객체 st 선언
		int N = Integer.parseInt(st.nextToken());
		// int형 변수 N를 선언하고 공백을 기준으로 값을 입력
		int M = Integer.parseInt(st.nextToken());
		// int형 변수 M를 선언하고 공백을 기준으로 값을 입력

		arr = new int[M];
		//  배열 arr의 길이를 M으로 함
		check = new boolean[N];
		// 배열 check의 길이를 N으로 함
		btm(N, M, 0);
		// 메소드 btm 호출
		System.out.println(sb);
		// sb 출력
	}

	public static void btm(int N, int M, int depth) {
	// 메소드 btm 선언, 매개변수 N, M, depth를 가짐
		if (depth == M) {
		// 변수 depth가 M과 같을 때 괄호안에 코드 실행
			for (int val : arr) {
			// 배열 arr의 길이 만큼 for문 반복
				sb.append(val).append(' ');
				// 변수 val의 내용 객체 st에 추가
			}

			sb.append('\n');
			// 객체 sb에 개행 추가
			return;
		}

		for (int i = 0; i < N; i++) {
		// i이 0~<N까지 반복
			if (!check[i]) {
			// check[i]가 0일때 괄호안의 코드 실행
				check[i] = true;
				// check 값에 true 저장
				arr[depth] = i + 1;
				// arr[depth] 값에 i+1 저장
				btm(N, M, depth + 1);
				// 매개변수 N, M, depth + 1로 매소드 dfs 호출 
				check[i] = false;
				// visit[i] 값 안에 false 저장
			}
		}
	}
}

 

[4] 결과