반응형
이 문제는 재귀를 이용하여 원하는 조건을 출력하는 백트래킹 문제입니다.
이 문제를 풀 때 Arrays.sort를 이용하여 입력받은 배열들을 오름차순으로 정렬한 후에 푸시면 됩니다.
바로 코드를 보여드리겠습니다.
import java.io.*;
import java.util.*;
public class Main{
static int[] intArr;
static int[] dfsArr;
static boolean[] visited;
static int N;
static int M;
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());
intArr = new int[N];
dfsArr = new int[M];
visited = new boolean[N];
st = new StringTokenizer(br.readLine());
for(int i = 0; i<N; i++)
intArr[i] = Integer.parseInt(st.nextToken());
Arrays.sort(intArr);
dfs(0);
}
static void dfs(int cnt){
if(cnt == M){
for(int i = 0; i<M; i++)
System.out.print(dfsArr[i]+" ");
System.out.println();
return;
}
for(int i = 0; i<N; i++){
if(!visited[i]) {
dfsArr[cnt] = intArr[i];
visited[i] = true;
dfs(cnt+1);
visited[i] = false;
}
}
}
}
반응형
'알고리즘 > 백트래킹' 카테고리의 다른 글
백준 15657번 : N과 M (8) java (0) | 2022.06.10 |
---|---|
백준 15663번 : N과 M (9) java (0) | 2022.06.03 |
백준 14889번 : 스타트와 링크 java (0) | 2022.05.25 |
백준 9663번 : N-Queen java (0) | 2022.05.25 |
백준 14888번 : 연산자 끼워넣기 java (0) | 2022.05.24 |
댓글