공부 154일차: 백준 15651번 N과 M (3) 자바 java

15651 N과 M (3)

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

15651번: N과 M (3)

 

 

 

 

---

백준 15651번 문제 N과 M (3)

---

문제

---

 

 

 

 

---

과정 생각해보기

---

 

https://gimbalja.tistory.com/290

공부 152일차: 백준 1748번 N과 M (1) 자바 java

 

N과 M 3번째 문제

 

 

추가된 조건은

• 1부터 N까지 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.

그래서 이런 식으로 출력되어야 한다

 

이를 위해서는,

N과 M(1) 문제 코드에서 DFS를 재귀호출하는 부분의 순서만 바꿔주면 된다

재귀 호출하기 전에 false로 선언하여 이전에 들어갔던 숫자도 arr에 들어갈 수 있도록 만들어준다

 

DFS 코드의 실행 과정을 직접 써본다면 이해하는 데에 도움이 될 것이다

 

 

 

 

 

---

정답 인정 코드

---

 

1)

import java.io.*;
import java.util.StringTokenizer;
 
public class Main {
    
    static int n, m;
    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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        
        arr = new int[m];
        visited = new boolean[n];
        
        DFS(0);
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }
    
    static void DFS(int depth) {
        if(depth == m) {
            for(int num : arr) {
                sb.append(num).append(' ');
            }
            sb.append('\n');
            return;
        }
        
        
        for(int i = 0; i < n; i++) {
            if(!visited[i]) {
                visited[i] = true;
                arr[depth] = i+1;
                visited[i] = false;    // 재귀를 호출하기 전에 false로 바꾸면 중복 숫자도 들어간다
                DFS(depth+1);
            }
        }
    }
 
}
 

 

정말로 순서만 바꾸면 정답 처리되는 문제이다

 

 

2)

import java.io.*;
import java.util.StringTokenizer;
 
public class Main {
    
    static int n, m;
    static int[] arr;
    static StringBuilder sb = new StringBuilder();
 
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        
        arr = new int[m];
        
        DFS(0);
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }
    
    static void DFS(int depth) {
        if(depth == m) {
            for(int num : arr) {
                sb.append(num).append(' ');
            }
            sb.append('\n');
            return;
        }
        
        
        for(int i = 0; i < n; i++) {
            arr[depth] = i+1;
            DFS(depth+1);
        }
    }
 
}

 

아니면 아예 visitsed를 만들지 않고 모든 숫자를 지나가게 만들면 된다

 

 

 

---