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

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

15654번: N과 M (5)

 

-문제해설

dfs를 이용해야 하고 방문함수를 사용해서 이전 깊이에서 방문한 수는 건너뛰도록 해야한다.

그리고 다시 이전 깊이로 돌아오면(백트래킹) 방문함수를 다시 미방문 처리해줘야 한다.

 

n과 m(1) 문제와 비슷하니 참고..!

다른 점은 사용될 숫자를 입력받고 정렬을 해야 된다는 점이다.

 

 

 

-자바

package bruteforce;

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

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

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

 

-파이썬

from sys import stdin

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

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

arr = list( map(int, input().split()) )
arr.sort()

dfs( 0 )