[백준,BOJ 15649] N과 M(1) (JAVA 구현)

 

-내 생각

  우선 알고리즘 공부를 시작하고 순열 문제를 처음 접했다. 여러 글을 읽어보던 중 순열과 조합의 차이를 알 수 있었고, 이번 문제는 그 순열에 관한 문제였다. DFS와 백트래킹을 이용하라고 하는데 아직까지는 개념이 잡히질 않는다. DFS의 경우에는 한 가지를 고정한 후 가능한 경우의 수를 찾고 또 그 경우의 수에서 한 가지를 고정하고 하위 경우의 수를 찾고... 갖은 개념으로 알고 있으며 백트래킹은 이러한 과정에서 어떠한 조건에 걸리지 못하면, 다 배제를 해버리는 탐색으로 완전 탐색과는 다른 개념으로 알고 있다.

 

  문제의 이해는 쉬웠지만 어떻게 구현해야 할지 감이 잡히질 않아서 다른 분들의 블로그 글들을 많이 참고했다.

 

-해법

 dfs메서드에 반복 횟수를 인자로 전달한다. 0번부터 전달하는 이유는 결과 배열에 0번 인덱스부터 저장하기 위함이며, 예제 2번을 통해 결과를 유추해보면

  1. 최초 실행 시 dfs에 0이 전달되면서 1부터 n까지 탐색을 한다.

  2. 초기 상태이므로 1은 방문하지 않은 상태이기 때문에 check [1]을 방문처리

  3. 현재 반복 횟수가 0번째이므로 list [0] = 1이 된다.

  4. 반복 횟수를 +1 후 다시 전달한다. (즉 list에 [0] 번째 자리가 찼으므로 다음 자리를 찾는 과정)

  5. 2번째 자리부터는 다시 1부터 탐색한다. (1번 과정) 그러나 list [0]에는 1이 존재하고, 그에 따라 check [1] 역시 방문         처리되어있다. 그렇기 때문에 다음 탐색 대상인 2를 고려해 본다.

  6. 2는 한 번도 방문하지 않았기 때문에 check [2] = 1(2번 과정), list [1] = 2가 된다. (3번 과정)

  7. 이후 다시 반복 횟수를 증가시킨다. 그러나 m이 2이기 때문에 DFS메서드 종료부에 걸려 현재 list의 원소들을 모두         출력한다. (cnt=2인 상태에서 종료되었으므로 다시 cnt는 1인 상태를 고려한다. cnt가 1인 상태에서는 2번까지 탐색       후 DFS메서드를 실행했으므로 아래 부분인 check [2] = 0을 진행)

  8. 즉 1은 고정된 상태로 n까지 반복하면서 2번째 자리를 변경시켜주는 과정을 진행 후 다 찾으면 cnt가 0인 상태로         돌아가 2번을 탐색하기 때문에 list [0]은 2로 고정되고 위 과정을 반복한다.

  

 

import java.util.*;

public class Main {
	static int m,n; // N과 M을 입력받는다.
	static int list[],check[]; // 숫자의 방문여부를 체크 할 방문배열과 결과를 저장 할 배열을 선언
	
	static void dfs(int cnt) { // DFS메소드, 반복횟수를 인자로 받는다. 초기 0부터 시작
			
		if(cnt == m) { // 0부터 M번까지 반복했으면 하나의 처리가 완성
        			   // 개인적인 생각으로는 이부분이 백트래킹에 해당한다고 생각한다.
                       // M보다 큰 횟수는 고려하지 않고 배제한다.
			for(int i=0;i<m;i++) { // 현재 결과배열을 출력
				System.out.print(list[i]+" ");
			}
			System.out.println("");
			return; // DFS 종료 
		}
		
		for(int i =1;i<=n;i++) { // 수의 범위는 1부터 N까지이다.
			
			if(check[i]==1) continue; // 이미 방문한 배열이면 건너뛴다.
			check[i]=1; // 방문하지 않았다면, 방문처리 후
			list[cnt]=i; // 현재 반복횟수에 해당하는 배열에 i값을 넣는다.
			dfs(cnt+1); // 반복횟수를 증가시킨다.
			check[i]=0; // dfs가 종료 후에는 다시 방문여부를 0으로 초기화한다.
			
			
		}
		
		
	
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);	
		
		n = sc.nextInt(); 
		m = sc.nextInt(); 
		
		check = new int[9]; // n과 m의 최대범위
		list = new int [9];
		dfs(0);
	}
	
}