[백준 15649] N과 M (1) (자바)

백준 15649번 N과 M (1) (자바)

 

 

출처

www.acmicpc.net/problem/15649

15649번: N과 M (1)

 

 

 

문제

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

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

 

 

 

입력

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

 

 

 

출력

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

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

 

 

 

입출력 예

입출력 예 1

입출력 예 2

입출력 예 3

 

 

 

풀이

1. 완점탐색(dfs + 백트래킹)으로 풀어야 한다.

2. 방문처리를 통해 자기자신을 제외한 값들을 불러온다.

3. M개 까지 탐색을 마치면 값들을 출력하고 백트래킹을 통해 미방문 처리를 한다.

 

 

 

내 코드

package brute_force;

import java.util.Scanner;

public class N_15649 {
	
	private static int N, M;
	private static int[] arr;
	private static boolean[] visit;
	
	public static void main(String[] args) {
		
		// 1 ~ N까지 수 중 M개 고른 수열
		
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt();
		M = sc.nextInt();
		
		visit = new boolean[N+1];
		arr = new int[M];
		dfs(0);
		
	}

	private static void dfs(int d) {
		//M = 2
		if (d == M) {
			for (int i=0; i<M; i++) {
				System.out.print(arr[i] + " ");
			}
			System.out.println();
		} else {
			
			for (int i=1; i<=N; i++) {
				//이전에 visit[i]에 true를 해 1을 띄어넘음
				if (visit[i] == false) {
					visit[i] = true;
					arr[d] = i;
					//재귀
					dfs(d+1);
					//백트래킹
					visit[i] = false;
				}
			}
		}
		
		
	}
}

 

 

고려할 점

1. dfs 사용할 것

2. 방문처리를 한 후 자신을 제외한 재귀를 실행해 나머지 값들을 탐색

3. 백트래킹할 것