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

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

15651번: N과 M (3)

 

-문제해설

1부터 n까지의 숫자 중에서 m 길이만큼의 수열을 만드는데 오름차순이고 중복되는 숫자가 와도 되는 문제이다.

 

n과 m이 4 4 인 경우

1 1 1 1

1 1 1 2

1 1 1 3

1 1 1 4

1 1 2 1

.

.

.

4 4 3 4

4 4 4 1

4 4 4 2

4 4 4 3

4 4 4 4

를 출력하면 된다.

 

n=4, m=2라고 가정하자.

1. n과 m을 입력받고 수열을 담을 arr을 선언한다. arr배열의 크기는 m이다. 그리고 이 모든 변수는 전역변수이다.

 

2. dfs메소드의 매개변수로는 index는 index부터 n까지 반복되면서 arr에 담길 수이고,

depth는 dfs메서드를 재귀한 횟수이다. depth가 m과 같아지면 StringBuilder에 append시켜준다.

 

3. dfs( 1, 0 )으로 처음 호출한다.

for문에서 i=index이고,  index=1이므로 1부터 n까지 반복된다.

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

dfs( index, depth+1 ) = dfs( 1, 1 )

 

dfs(1, 1)에서

for문 i=index=1부터 n까지 반복

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

dfs( index, depth+1 ) = dfs( 1, 2 )

 

dfs( 1, 2 )에서 depth가 2 이므로 arr=[1, 1]를 sb에 append시키고

return돼서 dfs( 1, 1 )로 돌아간다.

 

dfs( 1, 1 ) 에서 i는 이제 2가 된다.

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

dfs( index, depth+1 ) = dfs( 1, 2 )

 

dfs( 1, 2 )에서 depth 2이므로 arr=[1,2]를 sb에 append시키고 

return 돼서 dfs( 1, 1 ) 다시 돌아간다.

 

이 과정을 반복하면 정답이 출력된다.

 

 

 

 

 

 

 

-자바

package bruteforce;

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

public class BJ15651 {
	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( index, 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
    if depth == m: 
        print( ' '.join( map(str, arr) ) )
        return
    
    for i in range( 1, n+1 ):
        arr[depth] = i
        dfs( i, depth+1 )

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