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

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

15649번: N과 M (1)

 

-문제해설

DFS를 이용해서 백트래킹을 구현하면 쉽게 풀 수 있는 문제이다.

처음에 이해가 어려운데 알고보면 간단하다.

 

예시와 같이 n=4, m=4라고 해보자.

 

1. n, m 입력받고 출력값을 담을 배열 arr, dfs의 방문처리를 위한 배열 visit를 전역변수로 선언하고

main메서드 안에서 초기화해준다.

 

2. dfs함수 호출 dfs( n, m, depth )

depth가 m이면, 즉 4이면 현재 arr에 담겨있는 수들을 sb에 append시킨다.

 

먼저 반복문 i=0 ~ i<n까지 순회한다.

depth가 0일 때

visit[depth] = visit[0] = true로 방문처리해준다.

그리고 arr[depth] = arr[0] 에는 i+1을 해주어 arr[0] = 1이 되게 한다.

arr = (1)

 

그리고 dfs함수를 재귀호출한다. dfs( n, m, depth+1 ) -> dfs( 4, 4, 1 )

 

그럼 depth = 1이 된 상태로 새로운 dfs함수로 들어오고

반복문 i=0 ~ i<n이 실행된다.

이때 visit[0] = true이므로 i = 1이된다.

visit[i] = visit[1] = true로 방문처리되고

arr[depth] = arr[1] = i + 1 = 1+1 = 2가 저장된다.

arr = (1, 2)

 

또 dfs함수를 재귀호출한다. dfs( 4, 4, 2 )

 

depth = 2에서 반복문 i=0 ~ i<n이 실행된다.

visit[0], visit[1] = true이므로 i는 2가 된다.

visit[i] = visit[2] = true로 방문처리되고

arr[depth] = arr[2] = i + 1 = 2+1 = 3이 저장된다.

arr= (1, 2, 3)

 

또 다시 dfs함수를 호출 dfs(4, 4, 3)

 

depth = 3에서 for문 실행

visit[i] = visiti[3] = true,

arr[depth] = arr[3] = i+1 = 3+1 = 4

arr = (1, 2, 3, 4)

dfs 함수 호출 dfs( 4, 4, 4 )

 

depth가 4이므로 현재까지 담은 arr 배열의 값들을 (1, 2, 3, 4) 모두 sb에 append시키고 return한다.

 

그러면 depth = 3일 때로 돌아가고 

visit[3] = false로 다시 미방문처리로 만든다.

for문을 빠져나가고 dfs( 4, 4, 3 )이 종료되어서 dfs( 4, 4, 2 )로 돌아온다.

 

dfs( 4, 4, 2 ) 에서 i가 2일 때였으니깐 visit[2] = false로 다시 미방문처리로 만들어준다.

i가 3이 되고 visit[3] = true가 되고 arr[depth] = arr[2] = i+1 = 3+1 = 4가 된다.

arr = (1, 2, 4, 4)

그리고 dfs( 4, 4, 3 )을 호출한다.

 

dfs(4, 4, 3)에서 for문 반복한다.

i=0, 1일 때 visit[i] 는 모두 방문처리되어 있으므로

i = 2일 때 visit[i] = visit[2] = true로 방문처리되고 arr[depth] = arr[3] = i+1 = 2+1 = 3이 저장된다.

arr = (1, 2, 4, 3)

그리고 dfs( 4, 4, 4 )를 호출한다.

 

dfs(4, 4, 4)에서는 depth가 4이므로 arr담겨져있는 (1, 2, 4, 3) 값들을 sb에 append시켜주고

return한다.

 

그 다음은 dfs(4, 4, 2)가 모두 끝났으므로 dfs(4, 4, 1)로 다시 돌아가서 위 과정을 반복한다.

 

 

 

 

파이썬의 경우 permutation모듈을 이용해서 쉽게 구할 수 있다..;

 

 

-자바

package bruteforce;

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

public class BJ15649 {
	public static int[] arr;
	public static boolean[] visit;
	public static StringBuilder sb;
	
	public static void dfs( int n, int m, 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( n, m, depth+1 );
				visit[i] = false;
			}
		}
	}

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer( br.readLine() );
		int n = Integer.parseInt( st.nextToken() );
		int m = Integer.parseInt( st.nextToken() );
		
		sb = new StringBuilder();
		arr = new int[m];
		visit = new boolean[n];
		dfs( n, m, 0 );
		
		System.out.println( sb );
	}
}

 

-파이썬

from sys import stdin
from itertools import permutations
input = stdin.readline

n, m = map(int, input().split())
a = list( map( str, range( 1, n+1 ) ) )
print( '\n'.join( map( ' '.join, permutations(a, m) ) ) )