백준 15649번

N과 M 1

문제

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

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

입력

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

출력

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

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

예제

알고리즘 분류

• 백트래킹

코드

import java.util.*;
import java.io.*;

public class Main {
	public static int N;
	public static int M;
	public static int arr[];
	public static boolean visit[];
	public static StringBuilder sb= new StringBuilder();
	
	public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        
        arr = new int[M];
        visit = new boolean[N];
        
        dfs(0);
        System.out.println(sb);
    }
	
	public static void dfs(int depth) {
		if(depth == M) {
			for(int val : arr)
				sb.append(val).append(' ');
			
			sb.append('\n');
			
			return;
		}
		
		for(int i=0; i<N; i++) {
			if(!visit[i]) {
				visit[i] = true;
				arr[depth] = i + 1;
				dfs(depth + 1);
				visit[i] = false;
			}
		}
	}
}

풀이

이 문제의 경우, 백트래킹 문제로서, DFS를 활용하여 문제를 해결했다.

중복되는 수를 제외한 모든 경우의 수를 탐색하면 되기 때문에 재귀를 통해 해결하면 된다.

재귀를 하면서 이미 방문한 노드(값)이라면 다음 노드를 탐색하도록 하기 위해(유망한 노드인지 검사하기 위해) N 크기의 boolean 배열을 생성하고, 탐색과정에서 값을 담을 int 배열 arr 을 생성한다.

depth를 통해 재귀가 깊어질 때마다 depth를 1씩 증가시켜 M과 같아지면 더이상 재귀를 호출하지 않고 탐색과정 중 값을 담았던 arr 배열을 출력해주고 return을 해준다.

방문 상태를 판단하기 위해 visit[] 배열이 있는 것이고, 해당 index가 방문하지 않는 노드(값)일 때만 재귀호출을 해주면 된다.