🧩 Baekjoon □□□□ - N과 M(1 ~ 12)

N과 M(1)

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

public class Main {
	// 전역 변수
	static int n, m;
	static boolean[] visited;
	
	// 백트래킹 처리 메서드
	static void backtracking(int depth, String str) {
		if (depth == m) {
			System.out.println(str);
			return;
		}
		
		for (int i=1; i<n+1; i++) {
			if (!visited[i]) {
				visited[i] = true;
				backtracking(depth + 1, str + i + " ");
				visited[i] = false;
			}
		}
	}
	
	// 메인 메서드
	public static void main(String[] args) throws IOException {
		// 1. 변수 선언 및 초기화
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		visited = new boolean[n + 1];
		
		// 2. 백트래킹 처리
		backtracking(0, "");
	}
}

N과 M(2)

• 1부터 N까지 자연수 중에서 M개를 고른 수열
• 고른 수열은 오름차순이어야 한다.

// static void backtracking(int start, int depth, String str)
for (int i=start; i<n+1; i++) {
	if (!visited[i]) {
		visited[i] = true;
		backtracking(i+1, depth + 1, str + i + " ");
		visited[i] = false;
	}
}

• 수열이 오름차순이기 위해서는 현재 방문한 숫자보다 커야 하므로 Back-tracking 함수 호출 시 i + 1을 인자에 전달한다.

N과 M(3)

• 1부터 N까지 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.

public class Main {
	// 전역 변수
	static int n, m;
	static StringBuilder sb = new StringBuilder();
	
	// 백 트래킹 처리 메서드
	static void backtracking(int depth, String str) {
		if (depth == m) {
			sb.append(str).append("\n");
			return;
		}
		
		for (int i=1; i<n+1; i++) {
			backtracking(depth + 1, str + i + " ");
		}
	}
	
	// 메인 메서드
	public static void main(String[] args) throws IOException {
		// 1. 변수 선언 및 초기화
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		
		// 2. 백 트래킹 처리
		backtracking(0, "");
		
		// 3. 출력
		System.out.println(sb.toString());
	}
}

• 시간 초과 문제를 해결하기 위해 StringBuilder를 통해 문자열 연산을 처리하였다.
• visited 배열을 없애서 같은 수를 여러 번 고를 수 있게 하였다.

N과 M(4)

• 1부터 N까지 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.
• 고른 수열은 비내림차순이어야 한다.

// static void backtracking(int start, int depth, String str)
for (int i=start; i<n+1; i++) {
	backtracking(i, depth + 1, str + i + " ");
}

• N과 M (3) 문제에서 Back-tracking 메서드에 start 인자만 포함하면 된다.
• 비내림차순이어야 하므로 현재 방문한 노드부터 순회하게끔 start에는 i를 넣어주면 된다.

N과 M(5)

• N개의 자연수 중에서 M개를 고른 수열

public class Main {
	// 전역 변수
	static int n, m;
	static Set<Integer> visited;
	static List<Integer> nums;
	static StringBuilder sb = new StringBuilder();
	
	// 백 트래킹 처리 메서드
	static void backtracking(int depth, String str) {
		if (depth == m) {
			sb.append(str).append("\n");
			return;
		}
		
		for (int i: nums) {
			if (!visited.contains(i)) {
				visited.add(i);
				backtracking(depth + 1, str + i + " ");
				visited.remove(i);
			}
		}
	}
	
	// 메인 메서드
	public static void main(String[] args) throws IOException {
		// 1. 변수 선언 및 초기화
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st1 = new StringTokenizer(br.readLine());
		StringTokenizer st2 = new StringTokenizer(br.readLine());
		nums = new ArrayList<>();
		n = Integer.parseInt(st1.nextToken());
		m = Integer.parseInt(st1.nextToken());
		visited = new HashSet<>();
		
		// 2. 리스트 초기화
		for (int i=0; i<n; i++) nums.add(Integer.parseInt(st2.nextToken()));
		Collections.sort(nums);
		
		// 3. 백 트래킹 처리
		backtracking(0, "");
		
		// 4. 출력
		System.out.println(sb.toString());
	}
}

• List 안에 있는 요소들을 순회해야 하는데, 방문 여부를 인덱스로 관리할 수 없으므로 Set 자료구조를 통해 처리했다.

N과 M(6)

• N개의 자연수 중에서 M개를 고른 수열
• 고른 수열은 오름차순이어야 한다.

// static void backtracking(int start, int depth, String str)
int num = 0;
for (int i=start; i<n; i++) {
	num = nums.get(i);
	if (!visited.contains(num)) {
		visited.add(num);
		backtracking(i + 1, depth + 1, str + num + " ");
		visited.remove(num);
	}
}

오름차순 조건을 지키기 위해 N과 M (5) 문제에서 Back-tracking 메서드에 start 인자만 포함하면 된다.

N과 M(7)

• N개의 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.

// static void backtracking(int depth, String str)
for (int i : nums) {
	backtracking(depth + 1, str + i + " ");
}

• 같은 수를 여러 번 골라도 되므로 방문 여부를 처리하지 않아도 된다.

N과 M(8)

• N개의 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.
• 고른 수열은 비내림차순이어야 한다.

// static void backtracking(int start, int depth, String str)
int num = 0;
for (int i=start; i<n; i++) {
	num = nums.get(i);
	backtracking(i, depth + 1, str + num + " ");
}

• 같은 수를 여러 번 골라도 되므로 방문 여부를 처리하지 않아도 된다.
• 비내림차순이므로 start 인자에는 현재 방문한 인덱스를 전달한다.

N과 M(9)

• N개의 자연수 중에서 M개를 고른 수열
• 입력된 자연수는 중복될 수 있다.

public class Main {
	// 전역 변수
	static int n, m;
	static boolean[] visited;
	static int[] nums;
	static Set<String> resultSet;
	static StringBuilder sb = new StringBuilder();
	
	// 백 트래킹 처리 메서드
	static void backtracking(int depth, String str) {
		if (depth == m && !resultSet.contains(str)) {
			resultSet.add(str);
			sb.append(str).append("\n");
			return;
		}
		
		for (int i=1; i<=n; i++) {
			if (!visited[i]) {
				visited[i] = true;
				backtracking(depth + 1, str + nums[i] + " ");
				visited[i] = false;
			}
		}
	}
	
	// 메인 메서드
	public static void main(String[] args) throws IOException {
		// 1. 변수 선언 및 초기화
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st1 = new StringTokenizer(br.readLine());
		StringTokenizer st2 = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st1.nextToken());
		m = Integer.parseInt(st1.nextToken());
		nums = new int[n + 1];
		visited = new boolean[n + 1];
		resultSet = new HashSet<>();
		
		// 2. 리스트 초기화
		for (int i=0; i<n; i++) nums[i + 1] = Integer.parseInt(st2.nextToken());
		Arrays.sort(nums);
		
		// 3. 백 트래킹 처리
		backtracking(0, "");
		
		// 4. 출력
		System.out.println(sb.toString());
	}
}

• 입력에 중복된 수가 있을 수 있으므로 nums와 visited를 배열로 선언하였다.

N과 M(10)

• N개의 자연수 중에서 M개를 고른 수열
• 고른 수열은 비내림차순이어야 한다.

// static void backtracking(int start, int depth, String str)
for (int i=start; i<=n; i++) {
	if (!visited[i]) {
		visited[i] = true;
		backtracking(i, depth + 1, str + nums[i] + " ");
		visited[i] = false;
	}
}

• N과 M (9) 문제에서 Back-tracking 메서드에 start 인자만 포함하면 된다.
• 비내림차순이어야 하므로 현재 방문한 노드부터 순회하도록 start에는 i를 넣어주면 된다.

N과 M(11)

• N개의 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.

public class Main {
	// 전역 변수
	static int n, m;
	static boolean[] visited;
	static int[] nums;
	static Set<String> resultSet;
	static StringBuilder sb = new StringBuilder();
	
	// 백트래킹 처리 메서드
	static void backtracking(int depth, String str) {
		if (depth == m) {
			if (!resultSet.contains(str)) {
				resultSet.add(str);
				sb.append(str).append("\n");
			}
			return;
		}
		
		for (int i=1; i<=n; i++) {
			backtracking(depth + 1, str + nums[i] + " ");
		}
	}
	
	// 메인 메서드
	public static void main(String[] args) throws IOException {
		// 1. 변수 선언 및 초기화
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st1 = new StringTokenizer(br.readLine());
		StringTokenizer st2 = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st1.nextToken());
		m = Integer.parseInt(st1.nextToken());
		nums = new int[n + 1];
		visited = new boolean[n + 1];
		resultSet = new HashSet<>();
		
		// 2. 리스트 초기화
		for (int i=0; i<n; i++) nums[i + 1] = Integer.parseInt(st2.nextToken());
		Arrays.sort(nums);
		
		// 3. 백트래킹 처리
		backtracking(0, "");
		
		// 4. 출력
		System.out.println(sb.toString());
	}
}

• 다음 코드 때문에 재귀 함수 호출 깊이가 너무 깊어지면서 StackOverflowError 발생

if (depth == m && !resultSet.contains(str)) {
	resultSet.add(str);
	sb.append(str).append("\n");
	return;
}

• 이미 세트에 있는 값일 경우 return을 하지 않고 있기 때문에 다음 코드로 수정하였다.

if (depth == m) {
	if (!resultSet.contains(str)) {
		resultSet.add(str);
		sb.append(str).append("\n");
	}
	return;
}

N과 M(12)

• N개의 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.
• 고른 수열은 비내림차순이어야 한다.

// static void backtracking(int start, int depth, String str)
for (int i=start; i<=n; i++) {
	backtracking(i, depth + 1, str + nums[i] + " ");
}

• 비내림차순이어야 하므로 start를 추가하여 i를 인자로 넘겨주었다.