👀 문제
https://www.acmicpc.net/problem/15649
👊 도전
풀이 방법 1
1. 설계
- 1~n까지의 수 중에 중복 없이 m개를 고른 수열을 출력해야하므로 dfs를 이용한다.
2. 구현 (성공 코드)
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
import java.util.Scanner;
/**
*
* @author HEESOO
*
*/
public class Main {
static boolean[] visit;
static int[] array;
public static void dfs(int n, int m, int cnt){
if(cnt==m){
for(int i=0;i<m;i++){
System.out.print(array[i]+" ");
}
System.out.println();
return;
}
for(int i=1;i<=n;i++){
if(visit[i]) continue;
visit[i]=true;
array[cnt]=i;
dfs(n, m, cnt+1);
visit[i]=false;
}
}
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
int n=input.nextInt();
int m=input.nextInt();
visit=new boolean[n+1];
array=new int[n+1];
dfs(n, m, 0);
}
}
3. 결과
🤟 성공 🤟
4. 설명
- DFS를 이용한다.
- 순열을 구하는 문제이므로 DFS를 이용한다.
- 중복을 제외하기 위해 visit[]를 이용하여 이미 사용한(방문한) 숫자는 true로 저장한다.
- 출력할 숫자들을 저장하기 위해 array[]를 이용한다.
- 1부터 n까지 확인하면서 방문했다면 다음 숫자로 이동, 아니라면 방문했음을 나타내는 true를 저장한 후, array[]에 해당 숫자를 저장한다.
- 이후 다시 재귀호출하되, 숫자가 cnt+1개 사용되었으므로 이에 유의하여 파라미터를 넘겨준다.
- 사용 갯수 cnt가 m과 같아지면 저장된 array의 값들을 출력한 후, return을 통해 함수를 종료하고 재귀호출되었던 곳으로 돌아온다. 이 과정을 통해 깊이 우선 탐색(DFS)이 가능하게 된다.
- 재귀가 종료되면 해당 깊이에서의 계산이 끝났고, 다음 사용을 위해 visit[]를 false로 바꾸어 이후에 다시 방문 가능하도록 한다.
👏 해결 완료!
참고
- [백준,BOJ 15649] N과 M(1) (JAVA 구현) https://fbtmdwhd33.tistory.com/36
- [JAVA] 백준 알고리즘 15649번 문제풀이 (N과M) https://choseongho93.tistory.com/155