[백준 15649] N과 M (1) (JAVA)/백트래킹

[백준 15649] N과 M (1) (JAVA)/백트래킹

import java.io. * ;

import java.util. * ;

public class Main {

public static int N;

public static int M;

public static int arr[];

public static boolean visit[];

public static StringBuilder sb = new StringBuilder();

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];

visit = new boolean [N]; //숫자의 방문여부를 체크한다

dfs( 0 ); //dfs, 초기 0부터 시작한다

System . out . println (sb); //최종 답을 뽑아낸다

}

public static void dfs( int depth) {

if (depth = = M) { //깊이가 M과 같을때

for ( int i = 0 ; i < arr. length ; i + + ) {

sb.append(arr[i]).append( ' ' ); //sb에 저장한다

}

sb.append( '

' );

return ; //밑에 dfs()다음으로 넘어가 방문했던 곳을 false로 set 해준다

}

for ( int i = 0 ; i < N; i + + ) {

if ( ! visit[i]) { //배열에 방문을 하지 않았다면

visit[i] = true ; //방문 처리를 한다

arr[depth] = i + 1 ; //arr에 값을 추가해준다

dfs(depth + 1 ); //깊이를 늘려분다

visit[i] = false ; //return 되었을때 배열 방문여부를 false로 set 해준다

}

}

}

}

from http://programmer-note.tistory.com/2 by ccl(A) rewrite - 2021-08-19 18:26:31