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

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

15650번: N과 M (2)

 

-문제해설

가능한 조합들 중에서 오름차순으로 출력해야한다.

따라서 dfs 매개변수에 현재 수, 깊이를 넘겨준다.

dfs( int index, int depth )

 

만약 n = 4, m = 2일 경우

맨 처음 dfs( 1, 0 ) 호출한다.

 

아래 구문에 의해서 i가 1일 때부터 n(=4)까지 순회한다.

for( int i=index; i<=n; i++ ) {
    arr[depth] = i;
    dfs( i+1, depth+1 );
}

arr[depth] = arr[0] = 1  ( arr = (1) )

 

dfs( 2, 1 ) 호출

i = 2부터 4까지 순회

arr[depth] = arr[1] = 2 ( arr = (1, 2) )

 

dfs( 3, 2 ) 호출

dfs메서드 안에 아래 구문에 의해서 sb에 append된다.

if( depth == m ) {
	for( int val : arr ) sb.append( val ).append( " " );
	sb.append( "\n" );
	return;
}

 

다시 dfs(2, 1)로 돌아와서 i = 3이된다.

arr[depth] = arr[1] = 3 ( arr = (1, 3) )

 

dfs( 3, 2 ) 호출

depth가 2이므로 sb에 append된다.

 

다시 dfs(2, 1)로 돌아와서 i = 4가 된다.

arr[depth] = arr[1] = 4 ( arr = (1, 4) )

 

dfs( 3, 2 ) 호출

depth가 2이므로 sb에 append된다.

 

이번에는 dfs( 1, 0 )으로 돌아와서

i = 2가 된다.

arr[depth] = arr[0] = 2  ( arr = (2, 4) )

 

dfs(3, 1) 호출

i = 3일 때

arr[depth] = arr[1] = 3 ( arr = (2, 3) )

 

dfs( 4, 2 ) 호출

depth가 2이므로 sb에 append된다.

 

이런식으로 계속 진행해나가면 된다.

 

 

 

-자바

package bruteforce;

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

public class BJ15650 {
	static int n, m;
	static int[] arr;
	static StringBuilder sb = new StringBuilder();
	
	public static void dfs( int index, int depth ) {
		if( depth == m ) {
			for( int val : arr ) sb.append( val ).append( " " );
			sb.append( "\n" );
			return;
		}
		
		for( int i=index; i<=n; i++ ) {
			arr[depth] = 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[m];
		
		dfs( 1, 0 );
		
		System.out.println( sb );
	}
}

 

-파이썬

from sys import stdin

def dfs( index, depth ):
    global n, m, arr, s
    if depth == m:
        for val in arr: s += str(val)+" "
        s += "\n"
        return
    
    for i in range( index, n+1 ):
        arr[depth] = i
        dfs( i+1, depth+1 )

input = stdin.readline
n, m = map(int, input().split())
arr = [0]*m
s = ""
dfs( 1, 0 )
print( s )