[브루트포스, 백트래킹] 백준 - N과 M (6)

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

15655번: N과 M (6)

 

-문제해설

depth가 0일 때의 값만 방문처리해주고 나머지 depth에서는 방문처리없이 미방문된 숫자만 ans 배열에 추가해주고

마지막에 depth가 m과 같으면 ans배열값들을 모두 출력해주면 된다.

 

 

-자바

package bruteforce;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BJ15655 {
	static int n, m;
	static int[] arr, ans, visit;
	static StringBuilder sb = new StringBuilder();
	
	public static void dfs( int start, int depth ) {
		if( depth == m ) {
			for( int val : ans ) sb.append( val ).append( " " );
			sb.append( "\n" );
			return;
		}
		
		for( int i=start; i<n; i++ ) {
			if( depth == 0 ) {
				ans[depth] = arr[i];
				visit[i] = 1;
				dfs( i+1, depth+1 );
			}
			if( visit[i] != 1 ) {
				ans[depth] = arr[i];
				dfs( i+1, depth+1 );
			}
		}
		
	}

	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[n];
		visit = new int[n];
		ans = new int[m];
		
		st = new StringTokenizer( br.readLine() );
		for( int i=0; i<n; i++ ) arr[i] = Integer.parseInt( st.nextToken() );
		Arrays.sort( arr );
		
		dfs( 0, 0 );
		
		System.out.println( sb );
	}
}

 

-파이썬

from sys import stdin

def dfs( start, depth ):
    global n, m, arr, ans, visit
    if depth == m:
        print( ' '.join( map(str, ans) ) )
        return
    
    for i in range( start, n ):
        if depth == 0:
            visit[i] = True
            ans[depth] = arr[i]
            dfs( i+1, depth+1 )
            
        if visit[i]:
            pass
        else: 
            ans[depth] = arr[i]
            dfs( i+1, depth+1 )
            

input = stdin.readline
n, m = map(int, input().split())
arr = list( map(int, input().split()) )
arr.sort()
ans = [0] * m
visit = [False] * n
dfs( 0, 0 )