백준 - N과M(1) 15649 (백트래킹)

---

문제 분석

겹치는 수를 제외하고 재귀를 이용해서 풀면 되는걸로 이해했다. 해당 길이가 되면 return해주고 그렇지 않다면 1씩 증가하면서 재귀를 타도록 했다.

 

 

 

 

 

전체 소스

package test;

import java.util.*;
import java.io.*;

import java.util.*;

public class Main {

	static int N, M;
	static int[] pick;
	static boolean[] visited;
	static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		pick = new int[M];
		visited = new boolean[N];
		dfs(0, 0);
		System.out.println(sb);
	}

	public static void dfs(int start, int depth) {

		if (depth == M) {
			for (int i = 0; i < M; i++) {
				sb.append(pick[i]).append(' ');
			}
				sb.append('\n');
			return;
		}

		else {
			for (int i = 0; i < N; i++) {
				if (!visited[i]) {
					visited[i] = true;
					pick[depth] = i + 1;
					dfs(start + 1, depth + 1);
					visited[i] = false;
				}
			}
		}

	}

}

 

 

 

 

 

---

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

15649번: N과 M (1)

문제