[백준/JAVA] 15654번: N과 M (5)

🔺 문제

15654번: N과 M (5)

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int N, M;
    static int[] numbers; // 입력값 숫자 저장 배열
    static int[] arr; // 현재까지 선택한 숫자 저장 배열
    static boolean[] visited; // 중복 방지 위한 방문 저장 배열
    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());
        
        numbers = new int[N];
        arr = new int[N];
        visited = new boolean[N];
        
        st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0 ; i < N ; i++) {
            numbers[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(numbers);    // 오름차순 정렬
        
        dfs(0);
        System.out.println(sb);
    }
    
    private static void dfs(int depth) { // depth : 현재까지 선택한 숫자 개수
        if(depth == M) {
            for(int i = 0 ; i < M ; i++) {
                sb.append(arr[i] + " ");
            }
            sb.append("\n");
            return;
        }
        
        for(int i = 0 ; i < N ; i++) {
            if(!visited[i]) {
                visited[i] = true;
                arr[depth] = numbers[i];  // 🔔 변경된 부분 🔔
                dfs(depth + 1);
                visited[i] = false;
            }
        }
    }
}

✅ 해결 아이디어
✔ 백트래킹 (DFS)
- 사전 순으로 증가하는 순서로 출력해야 하므로 배열을 오름차순 정렬!

 

재귀함수 돌면서 arr[depth] = i 값을 넣어보면 이렇게...

---

💬 느낀 점

dfs(0)이 아니라 dfs(numbers[0])을 해야하는거 아닐까? 했는데

dfs(0)으로 해야 처음부터 시작해서 숫자를 선택해가면서 dfs 함수를 재귀적으로 호출하는 것.이라고

챗 gpt가 알려줬다!

1회독	2회독	3회독	4회독	5회독
V	8.29

 

 

(+ 2회독 : 8.29)

import java.util.*;
import java.io.*;
 
public class Main {
    static int N, M;
    static int[] A, result;
    static boolean[] visited;
    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());
        
        A = new int[N];
        st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0 ; i < N ; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(A);
        
        result = new int[M];
        visited = new boolean[N];
        
        back(0);
        System.out.println(sb);
    }
    
 
    private static void back(int depth) {
        if(depth == M) {
            for(int i : result) sb.append(i).append(" ");
            sb.append("\n");
            return;
        }
        
        for(int i = 0 ; i < N ; i++) {
            if(!visited[i]) {    // 같은 수 중복 제거
                result[depth] = A[i];
                
                visited[i] = true;
                back(depth + 1);
                visited[i] = false;
            }
        }
    }
}