[백준,BOJ 15649] N과 M(2) (JAVA 구현,추가풀이)

 

-내 생각

  백준 15649번 문제인 N과 M(1)이 순열을 출력하는 문제였다면, 이번 문제는 조합을 출력하는 문제였다. 어떤 블로그에서 봤던 글에 의하면 순열과 조합 문제는 DFS를 이용해 구현하면서, 순열의 경우에는 순열의 끝을 기준으로 재귀 호출을 종료하며, 조합의 경우에도 재귀 호출을 종료하는 조건은 같지만, 중간 처리 부분에서 하나의 인자가 더 필요하다는 것을 알 수 있었다. 하지만 글을 자세히 보지 않아 어떤 인자가 들어가야 할지 고민해보다 순열은 매 순간마다 1부터 끝 숫자까지 탐색해야 하고 조합은 (1,2)나 (2,1)을 같은 경우로 보기 때문에 매 순간마다 1부터 볼 필요가 없다는 사실을 떠올리고 반복문의 시작 부분을 변경해주면 될 것 같다는 큰 틀을 잡고 구현해보았다.

 

-해법

  이전에 N과 M(1)에서 사용했던 코드에서 반복문의 시작 부분만 수정해주면 된다. 자세한 내용은 코드의 주석을 통해 확인하자.

 

import java.util.*;

public class Main {
	static int m,n; // M과 N변수

	static int list[],check[]; // 결과를 저장 할 list배열과 방문 여부를 체크 할 방문 배열
	
	static void dfs(int idx,int cnt) { // DFS메소드, 반복문의 시작부분을 변경해줘야 하므로 인자를 하나 더 추가한다.
  	
		if(cnt == m) { // 기존의 종료조건 이었던 수열의 끝에 도달하면 종료하는 부분은 동일하다.
			for(int i=0;i<m;i++) {
				System.out.print(list[i]+" ");
			}
			System.out.println("");
			return;
		}
		
		for(int i =idx+1;i<=n;i++) { // 반복문의 시작 부분을 변경해줘야 한다.
        							 // 초기에 시작할 때는 두번 째 자리는 1부터 N까지 탐색 
                                     // 2로 시작할 때는 두번 째 자리는 3부터 N까지 탐색
                                     // 3으로 시작할 때는 두번 째 자리는 4부터 N까지 탐색.. 반복이다.
			if(check[i]==1) continue; // 동일하다. 이미 방문한 경우는 넘긴다.
			check[i]=1; // 방문하지 않은 경우는 방문 처리 후
			list[cnt]=i; // cnt값의 자리는 i로 즉, 초기에는 0번인덱스(첫 번째 자리)는 1이다.
			dfs(i,cnt+1); // 현재의 i값보다 큰 경우를 탐색해야 하므로 i를 전달 후 반복문 시작부분에서 +1 해주는 것
			check[i]=0; // 모두 찾은 후에는 다시 방문 여부를 초기화
	
		}

	}
    
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);	
		
		n = sc.nextInt(); 
		m = sc.nextInt(); 
		
		check = new int[9];
		list = new int [9];
		dfs(0,0); // 초기의 시작은 1부터 N까지 탐색해야 하므로 0을 전달
	}
	
}

---

  이전에도 풀어봤던 문제이지만, 이번엔 N과 M(1) 문제를 풀고 보았더니, 규칙상 앞선 숫자의 뒤에 오는 숫자는 모두 앞선 숫자보다 크기 때문에 탐색의 시작을 변경해야 한다는 요점은 똑같았지만, 풀이는 좀 다르게 했다. 근데 사실상 똑같은 소리다.

import java.util.Scanner;

class Main {
	static int n,m;	
	static void dfs(int[] a,boolean[] check,int v,int cnt) {
		if(cnt == m) {
			for(int i=0;i<m;i++) {
				System.out.print(a[i]+" ");
			}
			System.out.println();
			
			return;
		}
		
		
		for(int i=v;i<check.length;i++) {
			if(!check[i]) {
				check[i] = true;
				a[cnt] = i;
                // 깊이 탐색 시 자신을 전달해 자신+1 부터 반복하면 자신보다 큰 수만으로 수열을 고려하게 된다.
                // 덩달아 자기 자신은 고려하지 않기 때문에 좀 더 빠르다.
				dfs(a,check,i+1,cnt+1); 
				check[i] = false;
			}
		}
	}
	
	public static void main(String[] args)  {
		Scanner in = new Scanner(System.in);
		
		n = in.nextInt();
		m = in.nextInt();
		
		int a[] = new int[m];
		boolean check[] = new boolean[n+1];
		
		dfs(a,check,1,0);
		
	}
}