[백준 알고리즘] 15649번 N과 M (1) (백트래킹)

안녕하세요 호호만두에요

이번에는 백준 알고리즘 15649번 N과 M (1) 문제에요

 

N과M 문제는 워낙 많아서 문제집으로도 만들어져있는데요

이번에 다 풀었어요!! 그 중에 제일 베이스가 되는 기본 문제인 15649번 N과 M 풀이 해보려구요

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

불러오는 중입니다...

 

이 문제는 백 트래킹을 이용하면 되는 문제에요

저는 재귀로 순열을 구해서 만들었어요

 

우선 배열에 1부터 n까지의 숫자를 담았어요

그리고 이 값을 가지고 재귀를 통해 모든 경우의 수를 따져주었어요

이때 '1 2'도 되고 '2 1'도 되기 때문에 순열을 찾아주면 됩니다

배열의 앞쪽 인덱스 부터 가능한 순열을 모두 찾으면 답이에요

 

배열을 순회하면서 output이라는 배열에 순열을 담고 출력하고를 반복하며 풀었습니다

코드는 아래 코드를 참고하시면 되요

	import java.io.BufferedReader;
	import java.io.IOException;
	import java.io.InputStreamReader;
	class Main{
	public static void main(String[] args) throws IOException{
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	String[] temp = br.readLine().split(" ");
	int n = Integer.parseInt(temp[0]);
	int m = Integer.parseInt(temp[1]);
	boolean[] visited = new boolean[n];
	int[] arr = new int[n];
	int[] output = new int[m];
	// 배열 생성
	for(int i=1; i<=n; i++) {
	arr[i-1] = i;
	}
	permu(arr, output, visited, 0, n, m);
	br.close();
	}
	public static void permu(int[] arr, int[] output, boolean[] visited, int depth, int n, int r) {
	if(depth== r) {
	print(output, r);
	return;
	}
	for(int i=0; i<n; i++) {
	if(visited[i] != true) {
	visited[i] = true;
	output[depth] = arr[i];
	permu(arr, output, visited, depth +1 , n, r);
	visited[i] = false;
	}
	}
	}
	static void print(int[] arr, int r) {
	for(int i=0; i<r; i++)
	System.out.print(arr[i] + " ");
	System.out.println();
	}
	}

view raw BOJ15649.java hosted with ❤ by GitHub

 

 

잘 모르겠거나 이해안가는 부분 있으면 알려주세요!!