[BOJ/Java] 15666. N과 M(12)

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

 

 

 

• 수열들을 비교했을 때, 앞에서 부터 비교했을 때 오름차순이 되어야한다. 

 

 

접근

• 순차적으로 모든 원소를 방문한다고 생각하고 필요없는 부분을 제거하는 백트래킹 가지치기를 하면 된다.
• 순회 원소를 선택할 때, 중복이 없도록 고려하자.

 

가지 치기

• 만약 1을 선택했다면 다음 원소는 다음 자리 수에 원소부터 골라야한다. 

 

• 다른 가지에서 중복된 값을 선택하지 않아야 한다. (같은 줄 == depth에서) 

전체를 순회하는 재귀 탐색 코드에서 위에 해당하는 가지를 제외시키면 정답이 된다. 

 

코드

단순히 전체를 순회한다면 아래와 같은 코드

if(depth == M) {
    for(int n : nums) sb.append(n).append(" ");
        sb.append("\n");
    } else {
            for(int i = 0; i < N; i++) {
                    dfs(i, depth+1);
            }
}

 

• 같은 Depth에서 중복되지 않도록 가지 제거

int before = 0; //같은 depth에 중복값이 들어가지 않도록 관리
    for(int i = idx; i < N; i++) {
        if(before != arr[i]) {
            nums[depth] = arr[i];
            before = arr[i];
            dfs(i, depth+1);
        } else continue;
    }
}

before을 원소 순회를 시작하면서 저장하기 때문에, 반복문에서(같은 depth) 에서 중복이 발생하지 않는다.

 

• 다른 가지에서 자리 수(idx) 다음부터 고르도록 가지치기

단순히 for(int i = 0; i < N; i++) {} 부분에서 for(int i = idx; i < N; i++) 로 바꿔서 다음 idx 부터 원소를 순회하도록 설정하면 된다. 

 

 

---

전체 코드

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

class Main {

    static int[] arr;
    static int[] nums;
    static int N;
    static int M;
    static StringBuilder sb;

    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());
        nums = new int[M];
        sb = new StringBuilder();
        arr = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        Arrays.sort(arr);
        dfs(0, 0);
        System.out.println(sb);
    }

    static void dfs(int idx, int depth) {
        if(depth == M) {
            for(int n : nums) sb.append(n).append(" ");
            sb.append("\n");
        } else {
            int before = 0; //같은 depth에 중복값이 들어가지 않도록 관리

            for(int i = idx; i < N; i++) {
                if(before != arr[i]) {
                    nums[depth] = arr[i];
                    before = arr[i];
                    dfs(i, depth+1);
                } else continue;
            }
        }
    }
}

 

 

ETC

이 문제를 자주 실수해서 조금 더 오래 기억하고자 기록한다.