[백준_15649번] N과 M (1)

https://www.acmicpc.net/problem/15649

15649번: N과 M (1)

[백트래킹]

 백트래킹이란 어떤 노드의 '유망성'을 판단한 뒤, 해당 노드가 유망하지 않다면 부모 노드로 돌아가 다른 자식 노드를 찾는 방법이다. 즉, 모든 경우의 수를 찾아보지만, 그 중에서도 가능성만 있는 경우의 수만 찾아보는 방법이다. 이러한 백트래킹은 DFS(깊이우선탐색), BFS(너비우선탐색) 등을 사용하여 구현할 수 있다.

 

[문제]

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

 

[입력 조건]

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

 

[코드]

import java.util.Scanner;

public class BaekJoon_15649 {
	public static int[] arr; // 값을 담을 배열
	public static boolean[] visit; // 유망한 노드인지 검사하기 위한 배열(재귀를 하면서 이미 방문한 노드라면 건너뛰기)
	public static StringBuilder sb=new StringBuilder();
	
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		
		int n=sc.nextInt();
		int m=sc.nextInt();
		
		arr=new int[m+1];
		visit=new boolean[n+1];
		dfs(n,m,0);
		System.out.println(sb);
    }
	
	public static void dfs(int n, int m, int depth) {
		/*
		 * 재귀가 깊어질때 마다 depth 변수를 1씩 증가시키고 이 값이
		 * m과 같아지면 탐색 과정 중 값을 담았던 arr 배열을 출력한다.
		 */ 
		if(depth==m) {
			for(int i=0;i<m;i++) sb.append(arr[i]+" ");
			sb.append("\n");
			return;
		}
		for(int i=1;i<=n;i++) {
			// 해당 노드(값)를 방문하지 않았다면
			if(!visit[i]) {
				visit[i]=true; // 해당 노드를 방문 상태로 변경
				arr[depth]=i; 
				dfs(n,m,depth+1);
				visit[i]=false; // 처리가 끝났다면 방문상태 다시 변경
			}
		}
	}
}

 

[고찰]

 처음 접해보는 백트래킹 문제여서 그런지 어떻게 풀어야할지 감이 잡히지 않았다. 그래서 백트래킹의 개념과 풀이 방법을 익히기 위해 여러 사람들의 코드를 참고하였다.

 위와 같은 문제는 출력해야 하는 값들을 트리 형식으로 생각하고, 깊이가 탐색하지 않아도 되는 조건에 도달하면 저장해 뒀던 값을 한번에 출력하는 방식은 DFS(깊이 우선 탐색)의 방법으로 백트래킹 문제를 해결한 것이다. 백트래킹을 아직 완벽하게 이해하지는 못한것 같아서 여러 문제를 접해봐야 할 것 같다.