알고리즘/백준
공부 156일차: 백준 15654번 N과 M (5) 자바 java
김발자~
2023. 1. 2. 10:28
반응형
15654 N과 M (5)
https://www.acmicpc.net/problem/15654
15654번: N과 M (5)
N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열
www.acmicpc.net
백준 15654번 문제 N과 M (5)
문제
과정 생각해보기
https://gimbalja.tistory.com/290
공부 152일차: 백준 1748번 N과 M (1) 자바 java
15649 N과 M (1) https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출
gimbalja.tistory.com
N과 M 4번째 문제
이 문제는 1번 문제와 유사하다
다른 점은 기존엔 1부터 n까지로 수열을 이뤘다면, 이번엔 주어지는 숫자들만 오름차순으로 출력해야 한다는 점이다
달라지는 점은 많지 않다
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
public static void DFS(int depth) {
// 입력된 숫자의 깊이까지의 배열 출력
if(depth == m) {
for(int val : arr) {
bw.write(val+" ");
}
bw.newLine();
return; // 멈추기
}
for(int i = 0; i < n; i++) {
// 방문하지 않은 노드라면
if(!visited[i]) {
visited[i] = true; // 방문상태로 변경 후
arr[depth] = i+1; // 그 깊이의 노드에 값 넣기
DFS(depth+1); // 다음 노드 : 깊이+1
visited[i] = false; // 다시 false로 돌려서 검사할 수 있도록
}
}
}
|
cs |
기존의 DFS에서
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
static int[] nums;
static void DFS(int depth) throws IOException{
if(depth == m) {
for(int val : arr) {
bw.write(val+" ");
}
bw.newLine();
return;
}
for(int i = 0; i < n; i++) {
if(!visited[nums[i]]) { // 이전 i 자리에 nums[i]를 넣어 입력 받은 숫자만 들어가도록
visited[nums[i]] = true;
arr[depth] = nums[i];
DFS(depth+1);
visited[nums[i]] = false;
}
}
}
|
cs |
주어진 숫자를 입력받을 배열을 생성한 뒤,i 자리에 그 배열을 넣어주면 된다
정답 인정 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
|
import java.io.*;
import java.util.*;
public class Main {
static int n, m;
static int[] arr;
static int[] nums; // 주어지는 수를 입력받기 위한 배열 생성
static BufferedWriter bw;
static boolean[] visited;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
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];
nums = new int[n];
visited = new boolean[10_001];
st = new StringTokenizer(br.readLine());
for(int i = 0; i < n; i++) {
nums[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(nums); // 사전순대로 출력하기 위해 오름차순 정렬
DFS(0);
bw.flush();
bw.close();
}
static void DFS(int depth) throws IOException{
if(depth == m) {
for(int val : arr) {
bw.write(val+" ");
}
bw.newLine();
return;
}
for(int i = 0; i < n; i++) {
if(!visited[nums[i]]) { // 이전 i 자리에 nums[i]를 넣어 입력 받은 숫자만 들어가도록
visited[nums[i]] = true;
arr[depth] = nums[i];
DFS(depth+1);
visited[nums[i]] = false;
}
}
}
}
|
cs |
배열 추가해주고 기존 DFS의 i 자리에 그 배열만 넣으면 된다
유형이 다양해서 정답률도 높고, DFS에 대해 더 깊게 이해하게 되어 재미도 있다
반응형