[Baekjoon] 15664번 N과 M (10) (Java) 문제 풀이 [Sliver 2]

문제

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

15664번: N과 M (10)

 

어떻게 풀 것인가?

처음에는 단순 백트래킹을 이용한 조합 문제라고 생각했다.

하지만 다시보니 중복성을 제거 해야한다고 한다.

여기서 문제에 대해서 많이 생각을 했다.

결국 중복성에 대한 문제는 자료구조를 통해서 해결할 수 있었다. Set을 이용하기로 하였다.

조합을 이용한 백트레킹을 이용하였지만, 다른 사람의 풀이를 통해서 DFS 백트레킹을 이용하기로 하였다. 사실 큰 차이는 없는 것 같다.

 

풀면서 놓쳤던점

중복성을 고려못함.

 

이 문제를 통해 얻어갈 것

백트레킹

 

내 코드 

import java.io.*;
import java.util.*;

public class Main {
    public static int[] arr, ans;
    public static int N, M;
    public static boolean[] visit;
    public static StringBuilder sb = new StringBuilder();
    public static LinkedHashSet<String> set;

    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];
        ans = new int[N];
        set = new LinkedHashSet<>();
        st = new StringTokenizer(br.readLine());
        visit = new boolean[N];

        for (int i = 0; i < N; i++) {
            ans[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(ans);
        dfs(0, 0);
        set.forEach(System.out::println);
    }

    public static void dfs(int depth, int t) {
        if (depth == M) {
            StringBuilder sb = new StringBuilder();
            for (int val : arr) {
                sb.append(val).append(" ");
            }
            set.add(sb.toString());
            sb.append('\n');
            return;
        }
        for (int i = t; i < N; i++) {
            if (!visit[i]) {
                visit[i] = true;
                arr[depth] = ans[i];
                dfs(depth + 1, i + 1);
                visit[i] = false;
            }
        }
    }
}

 

참고

https://codingrapper.tistory.com/22

[BOJ - JAVA] 15664 - N과 M 10(백트래킹)