[Java] 백준 BOJ / 15663번: N과 M (9)

N과 M(9)

문제

알고리즘 설명

여러 N과 M 문제 중 이번 문제가 가지는 특징은 중복되는 수열을 여러 번 출력하면 안되는 조건이 있다는 점이다.

다른 문제들도 같은 조건이 있지만 이번 문제의 예제 입력을 보면 주어지는 수열에 중복되는 숫자들이 있다는 점을 유의하면 된다.

일단 전체 코드를 보면 아래와 같다.

코드

import javax.imageio.IIOException;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main_15663 {
    static int n, m;
    static int[] arr;
    static int[] result;
    static boolean[] visited;
    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[n];
        result = new int[m];
        visited = new boolean[n];


        st = new StringTokenizer(br.readLine());

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

        Arrays.sort(arr);

        dfs(0);
    }

    public static void dfs(int depth) {
        //수열 출력
        if (depth == m) {
            for (int val : result) {
                System.out.print(val + " ");
            }
            System.out.println();
            return;
        } else {
            int before = 0;
            for (int i = 0; i < n; i++) {
                if (visited[i]) {
                    continue;
                }

                if (before != arr[i]) {
                    visited[i] = true;
                    result[depth] = arr[i];
                    before = arr[i];
                    dfs(depth + 1);
                    visited[i] = false;
                }
            }
        }
    }
}

코드를 보면 다른 일반적인 N과 M 문제처럼 dfs로 풀었지만 중복 제거를 위해서 before라는 변수를 사용했다.

	int before = 0;
            for (int i = 0; i < n; i++) {
                if (visited[i]) {
                    continue;
                }

                if (before != arr[i]) {
                    visited[i] = true;
                    result[depth] = arr[i];
                    before = arr[i];
                    dfs(depth + 1);
                    visited[i] = false;
                }
            }

이 코드를 보면 처음에 before라는 변수를 선언한 후 일반적인 N과M처럼 result 배열을 채운 후에 그 배열을 채운 수를 before 변수에 저장한다.

before 변수는 같은 재귀 호출 깊이에서 중복된 숫자를 건너뛰기 위한 용도로 사용했다.
해당 코드에서 사용한 visited 배열은 같은 위치에서의 중복 선택만 방지하지만 이 배열은 같은 값에 대해 서로 다른 위치에서의 중복된 조합을 방지하지 못하기 때문에 before 변수를 사용했다.