15654 - N과 M 5(백트래킹)

15654 - N과 M 5(백트래킹)

# 주소

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

# 문제

# 문제 해설 및 코드 리뷰

import java.util.*; public class Main { public static boolean[] visit; public static int[] arr; public static int N, M; public static int[] ans; public static StringBuilder sb = new StringBuilder(); public static void main(String[] args) { Scanner in = new Scanner(System.in); N = in.nextInt(); M = in.nextInt(); arr = new int[M]; ans = new int[N]; visit = new boolean[N]; for(int i = 0; i < N; i++) { ans[i] = in.nextInt(); } Arrays.sort(ans); dfs(0); System.out.print(sb); } public static void dfs(int depth) { if (depth == M) { for (int val : arr) { sb.append(val + " "); } sb.append('

'); return; } for (int i = 0 ; i < N; i++) { if(!visit[i]) { visit[i] = true; arr[depth] = ans[i]; dfs(depth + 1); visit[i] = false; } } } }

이번엔 중복되지 않은 값을 출력해야 하므로 visit[]이라는 boolean 타입의 배열을 생성하여 방문한 위치에 대해서는 true로 바꾸고 재귀함수를 돌려야 합니다. 또한 모든 경우의 수의 값은 오름차순이므로 생성한 ans[]배열에 대해 Arrays.sort(ans)를 하여 오름차순으로 정렬한 뒤 arr에 삽입합니다.

그리고 dfs를 선언할 때 마다 depth + 1씩 증가시켜서 depth의 값이 M과 같아질 때마다 출력해주고 띄어쓰기를 진행하면 원하는 결과값을 얻을 수 있습니다.

from http://codingrapper.tistory.com/17 by ccl(A) rewrite - 2021-09-24 20:01:46