250x250
08-17 21:55
관리 메뉴

막내의 막무가내 프로그래밍 & 일상

[알고리즘] 백준 15664 N과 M(10) -백트래킹- 본문

알고리즘/DFS, BFS, 시뮬, 백트래킹

[알고리즘] 백준 15664 N과 M(10) -백트래킹-

막무가내막내 2021. 6. 20. 00:12
300x250
SMALL

 

 

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

 

15664번: N과 M (10)

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해

www.acmicpc.net

 

 

 

백준 백트래킹 대표문제 N과 M 시리즈 10번을 풀어봤습니다. ㅎㅎ

 

풀이는 다음과 같고 설명은 주석으로 대체했습니다.

 

[Java]

import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {
    private static int N;
    private static int M;
    private static int[] nums;
    private static StringBuilder sb = new StringBuilder(); //사용안하면 시간초과남
    private static Set set = new HashSet<String>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        nums = new int[N];
        for (int i = 0; i < N; i++) {
            nums[i] = sc.nextInt();
        }
        Arrays.sort(nums);
        boolean[] isVisited = new boolean[N];
        dfs(0, nums.clone(), isVisited);
        System.out.println(sb.toString());
    }

    private static void dfs(int depth, int[] arr, boolean[] isVisited) {
        if (depth == M) {
            StringBuilder sb2 = new StringBuilder();
            for (int i = 0; i < M; i++) {
                sb2.append(arr[i] + " ");
            }
            if(!set.contains(sb2.toString())) { //중복방지
                set.add(sb2.toString());
                sb.append(sb2.toString()).append("\n");
            }
            return;
        }
        int prev = -1;
        if (depth - 1 >= 0) {
            prev = arr[depth - 1];
        }
        for (int i = 0; i < N; i++) {
            if (prev <= nums[i] && !isVisited[i]) { // 오름차순의 경우만 + 중복되는 수열 여러번 출력 방지
                prev = nums[i];
                isVisited[i] = true;
                arr[depth] = prev;
                dfs(depth + 1, arr, isVisited);
                isVisited[i] = false;
            }
        }
    }
}

 

 

 

댓글과 공감은 큰 힘이 됩니다. 감사합니다. !!!

300x250
LIST
"이 포스팅은 쿠팡 파트너스 활동의 일환으로, 이에 따른 일정액의 수수료를 제공받습니다."
0 Comments
댓글쓰기 폼