[백준/JAVA] 15652번: N과 M (4)

🔺 문제

15652번: N과 M (4)

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int N, M;
    static int[] A;
    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[M];
        visited = new boolean[N];
        
        dfs(1, 0);
        System.out.println(sb);
    }
 
    private static void dfs(int at, int depth) { // at : 현재 위치
        if(depth == M) {
            for(int val : A) {
                sb.append(val + " ");
            }
            sb.append("\n");
            return;
        }
        
        for(int i = at ; i <= N ; i++) { // at부터 탐색 시작
            A[depth] = i; // 현재 깊이 위치에 i값 담기
            dfs(i, depth + 1);    // (🔔재귀) 오름차순 탐색
        }
    }
}

✅ 해결 아이디어
✔ 백트래킹 (DFS) : 수열 사전 순 증가 & 같은 수 여러번 가능
- 같은 수 여러번 골라도 된다. = 중복 허용
- 고른 수열은 비내림차순이어야 한다.
(* 비내림차순 : 리스트에 같은 수들이 존재할 수도 있는 오름차순 = 중복 가능한 오름차순)

 

N과 M (2) 랑 그냥 똑같다.

여기서 dfs 함수 재귀호출하는 부분에서 보내는 인자값 부분만 다르다. (35번째 줄)

 

인자를 dfs(i + 1, depth + 1)으로 하면 위 사진처럼 (1, 2) (1, 3) (1, 4) (2, 3), ... 이렇게 오름차순으로만 출력된다.

근데 본인이랑 같은 수도 같이 출력하면서 (1, 1) (1, 2) ... (2, 2), (2, 3)... 이렇게 가야 하니까 

dfs(i, depth + 1) 해주면 된다..

 

---

💬 느낀 점

별거 아닌데 헤맴,,,하하

 

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 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];
        for(int i = 0 ; i < N ; i++) {
            A[i] = i + 1;
        }
        
        result = new int[M];
        
        back(0, 0);
        System.out.println(sb);
    }
    
    private static void back(int startIdx, int depth) {
        if(depth == M) {
            for(int i : result) sb.append(i).append(" ");
            sb.append("\n");
            return;
        }
        
        // 조합, startIdx부터 시작
        for(int i = startIdx ; i < N ; i++) {
            result[depth] = A[i]; // 현재 깊이 위치에 A[i] 값 담기
            back(i, depth + 1);
        }
    }
}

 

---

(참고)

[백준] 15652번 N과 M (4) - Java, 자바

 

[ 백준 15652 / Java ] N과 M (4)