[BOJ/JAVA] N과 M(9) 백트래킹

문제

---

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

 

 

알고리즘 [접근 방법]

---

중복 값 입력처리 + 순열

각 수를 최대 몇번 사용 가능한지가 관건이였다

 

첫 번째 접근 visited로 비내림차순을 막으면 되지 않을까? 라 생각했다

N과 M(12)는 중복 제거 + 비내림차순이 핵심이라

초기에는 TreeMap과 visited 배열을 이용해 다음과 같이 생각했다.

• 입력 수를 정렬하고 중복 제거한다.
• 첫 번째 원소가 같은 수열이 여러 번 나오지 않게 visited로 막자.
• visited를 적절히 조절하면 비내림차순도 만들 수 있지 않을까?

결과는 완전히 실패였다 ㅠ

 

visited로는 비내림차순을 보장할 수 없다

비내림차순은 startIndex 기반 DFS가 해결해야 하는데

visited로 강제로 막으려고 하다 보니

5851 2643
908 5851 2643

이처럼 역순이 섞인 조합까지 등장했다.

 

그리고 정상 조합까지 visited에 의해 막혀버리며

오히려 visited가 다음 단계 DFS에서 필요한 선택까지 봉쇄해버렸다.

 

그 후 여러 시행착오 끝에 

distinct()를 활용하여 중복제거를 하고, visited를 쓰지않고 단순 dfs로만 백트래킹을 하여 문제를 풀어냈다

 

풀이

---

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

public class Main {
    static int N, M;
    static int[] num, arr;
    static int[] cnt = new int[10001];
    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());

        num = new int[N];
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++) {
            num[i] = Integer.parseInt(st.nextToken());
            cnt[num[i]] += 1;
        }
        num = Arrays.stream(num).distinct().toArray(); // 중복제거
        Arrays.sort(num); //정렬

        arr = new int[M];

        bfs(0);
        System.out.print(sb);
    }

    static void bfs(int m){
        if(m == M){
            for(int i = 0; i < M; i++) sb.append(arr[i]).append(" ");
            sb.append("\\n");
            return;
        }
        for(int i = 0; i < num.length; i++){
            if(cnt[num[i]] != 0) {
                arr[m] = num[i];
                cnt[num[i]]--;
                bfs(m + 1);
                cnt[num[i]]++;
            }
        }
    }
}

 

성능

---