백준 [15649] N과 M (1)

15649번: N과 M (1)

 

 

풀이

• 중복 없이 N개 중 M개를 골라야 한다.

조금 헷갈릴 수 있었던 부분이 [1, 2], [2, 1]은 중복되는 수열이라고 생각했었는데 순서가 달라서 다른 수열로 본다는 것을 나중에 이해했다..ㅋㅋ

 

한번 뽑은 수를 그 다음에 뽑지 않으면 중복을 없앨 수 있다.

방문 배열을 활용하여 한번 뽑은 수를 그 다음에 뽑지 않도록 체크를 해주어 중복 없이 M개를 뽑을 수 있다.

 

백트래킹 중 dfs를 사용하여 문제를 해결했다.

 

백트래킹 기법은 모든 경우의 수를 다 탐색하는 브루트 포스 방식과 다르게 유망성을 판단(조건을 주어)하여 조건에 걸리는 경우만 탐색하여 탬색 범위를 많이 줄이는 탐색 기법이다.

 

 

정답 코드

package com.baekjoon.p15649;

import java.util.*;

public class Main {
    static int n, m;
    static int[] arr, selected;
    static boolean[] visit;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        m = sc.nextInt();

        arr = new int[n]; // 뽑을 배열
        visit = new boolean[n];
        selected = new int[m];

        for (int i = 1; i <= n; i++) {
            arr[i - 1] = i;
        }

        pop(0);

        System.out.println(sb);
        sc.close();
    }

    private static void pop(int cnt) {
        if (cnt == m) {
            for (int i : selected) {
                sb.append(i + " ");
            }
            sb.append("\n");
            return;
        }

        for (int i = 0; i < n; i++) {
            if (!visit[i]) {
                visit[i] = true;
                selected[cnt] = i + 1;
                pop(cnt + 1);
                visit[i] = false;
            }
        }
    }
}