BOJ 15649 - N과 M (1)

입력

• 자연수 N과 M 입력 (1 ≤ M ≤ N ≤ 8)

출력

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 출력 (중복 X, 각 수열은 공백으로 구분해서 출력, 사전 순으로 증가하는 순서로 출력)

풀이 방법

• 백트래킹 이용
• visit 배열을 이용하여 방문한 숫자 체크
• 처음에는 [코드 1]처럼 작성하였으나 [코드 1]은 시간이 오래 걸리고 코드가 길어서 [코드 2]로 수정
  • [코드 1] : ArrayList를 이용하여 수열 저장
  • [코드 2] : ans 배열을 이용하여 수열 저장

코드

[코드 1] - ArrayList 사용

import java.util.*;

public class BOJ_15649 {
	static int N, M;
	static int[] visit;
	static ArrayList<Integer> list;
	
	public static void backtracking(int cur) {
		visit[cur]=1; // 현재 숫자에 방문했음을 체크
		list.add(cur); // arraylist에 현재 숫자 저장

		if(list.size()==M) { // M개의 숫자에 방문 완료했으면
			for(int i=0;i<list.size();i++) { // 수열 출력
				System.out.print(list.get(i)+" ");
			}
			System.out.println(); // 수열 구분
			return;
		}
		
		for(int i=1;i<N+1;i++) { // 반복해서 탐색
			if(visit[i]==0) { // 숫자 i에 아직 방문하지 않았다면
				backtracking(i); // 방문
				visit[i]=0; // 다음 탐색을 위해 다시 초기화
				list.remove(list.size()-1); // 다음 탐색을 위해 arraylist에서 해당 숫자 삭제
			}
		}
	}
	
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		N=sc.nextInt();	// 자연수 N 입력
		M=sc.nextInt();	// 자연수 M 입력
		visit=new int[N+1]; // 방문한 숫자 체크할 배열
		list=new ArrayList<Integer>(); // 수열 저장할 arraylist
		
		for(int i=1;i<N+1;i++) {
			list.clear(); // 새로운 탐색을 위해 arraylist 비우기
			
			backtracking(i); // 백트래킹
			visit[i]=0; // 다음 탐색을 위해 다시 초기화
		}
	}
}

[코드 2] - 배열 사용

import java.util.*;

public class BOJ_15649 {
	static int N, M;
	static int[] visit, ans;
	
	public static void backtracking(int cur, int cnt) {
		visit[cur]=1;	// 현재 숫자에 방문했음을 체크
		ans[cnt]=cur;	// 수열 배열에 현재 숫자 저장
		
		if(cnt==M) {	// M개의 숫자에 방문 완료했으면
			for(int i=1;i<M+1;i++) {	// 수열 출력
				System.out.print(ans[i]+" ");
			}
			System.out.println();	// 수열 구분
			return;
		}
		
		for(int i=1;i<N+1;i++) {// 반복해서 탐색
			if(visit[i]==0) {	// 숫자 i에 아직 방문하지 않았다면
				backtracking(i, cnt+1);	// 방문
				visit[i]=0;	// 다음 탐색을 위해 초기화
			}
		}
	}
	
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		N=sc.nextInt();	// 자연수 N 입력
		M=sc.nextInt();	// 자연수 M 입력
		visit=new int[N+1];	// 방문한 숫자 체크할 배열
		ans=new int[N+1];	// 수열 저장할 배열
		
		for(int i=1;i<N+1;i++) {
			backtracking(i, 1);	// 백트래킹
			visit[i]=0;	// 다음 탐색을 위해 다시 초기화
		}
		
		sc.close();
	}
}