Menu

Subscribe

[JAVA/백준] 백트래킹: N과 M (2)

HEESOO on Boj

👀 문제

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

👊 도전

풀이 방법 1

1. 설계

  1. 1~n까지의 수 중에 중복 없이 m개를 고른 수열을 출력해야하므로 dfs를 이용한다.
  2. 중복되는 수열을 여러 번 출력하면 안되고, 오름차순 정렬해야하므로 다음 출력할 자리의 숫자는 이전에 출력한 자리 숫자보다 크도록 하면 된다.

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
38
39

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, int idx){
		if(cnt==m){
			for(int i=0;i<m;i++){
				System.out.print(array[i]+" ");
			}
			System.out.println();
			return;
		}
		for(int i=idx;i<=n;i++){
			if(visit[i]) continue;
			visit[i]=true;
			array[cnt]=i;
			dfs(n, m, cnt+1, i+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, 1);
		
	}
}

3. 결과

실행결과 🤟 성공 🤟

4. 설명

  1. DFS를 이용한다.
    • 순열을 구하는 문제이므로 DFS를 이용한다.
    • 중복을 제외하기 위해 visit[]를 이용하여 이미 사용한(방문한) 숫자는 true로 저장한다.
    • 출력할 숫자들을 저장하기 위해 array[]를 이용한다.
    • 1부터 n까지 확인하면서 방문했다면 다음 숫자로 이동, 아니라면 방문했음을 나타내는 true를 저장한 후, array[]에 해당 숫자를 저장한다.
    • 이후 다시 재귀호출하되, 숫자가 cnt+1개 사용되었으므로 이에 유의하여 파라미터를 넘겨준다.
    • 사용 갯수 cnt가 m과 같아지면 저장된 array의 값들을 출력한 후, return을 통해 함수를 종료하고 재귀호출되었던 곳으로 돌아온다. 이 과정을 통해 깊이 우선 탐색(DFS)이 가능하게 된다.
    • 재귀가 종료되면 해당 깊이에서의 계산이 끝났고, 다음 사용을 위해 visit[]를 false로 바꾸어 이후에 다시 방문 가능하도록 한다.
  2. DFS()의 for문 범위를 조정하여 중복없는 오름차순을 구현한다.
    • 1 2를 출력하고 2 1을 출력하기 전에 1 2가 출력되었다는 것을 확안히가보다는, 다음에 출력할 자리의 숫자는 이전에 출력할 자리 숫자보다 크도록 조정하면 된다.
    • 따라서 마지막으로 넣은 숫자 i 다음 값을 파라미터로 넘기면서 재귀를 호출하면, 그 수부터 순열을 만들면 중복이 없는 오름차순을 출력할 수 있다.

👏 해결 완료!

참고