#15650: N과 M (2) [JAVA]

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

15650번: N과 M (2)

 

 

---

 

 

 

문제 접근

 

 

 

N과 M(1) 문제 복습하고 풀기

 

 

 

 

 

 

 

 

코드

 

 

 

 

1. N과 M(1) 문제에서 if문 한 줄 추가

 

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.io.IOException;

public class Main {

	static int n;
	static int m;
	static int[] arr; // 출력 위한 배열
	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());

		arr = new int[m];
		visited = new boolean[n];

		dfs(0);

		System.out.println(sb);

	}

	static void dfs(int depth) {

		if (depth == m) {
			for (int val : arr) {
				sb.append(val).append(' ');
			}
			sb.append('\n');
			return;
		}

		for (int i = 0; i < n; i++) {
			if (!visited[i]) {
				if (depth == 0 || i + 1 > arr[depth - 1]) { // 이전에 저장된 요소보다 크거나 첫 번째 저장될 요소여야함.
					visited[i] = true;
					arr[depth] = i + 1;
					dfs(depth + 1);
					visited[i] = false;
				}

			}
		}
	}
}

 

 

 

기본적으로 N과 M(1) 문제와 똑같이 dfs를 이용한 백트래킹 방식을 쓰고

 

오름차순으로 출력되기위해 단순하게 depth를 이용한 조건식을 중간에 넣었다.

 

 

 

 

 

 

 

 

 

2. 좀 더 간결하고 for문을 다 돌지 않도록

 

 

 

[ 참고 ] https://st-lab.tistory.com/115

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.io.IOException;

public class Main {

	static int n;
	static int m;
	static int[] arr; // 출력 위한 배열
	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());

		arr = new int[m];
		visited = new boolean[n];

		dfs(1, 0);

		System.out.println(sb);

	}

	static void dfs(int at, int depth) {

		if (depth == m) {
			for (int val : arr) {
				sb.append(val).append(' ');
			}
			sb.append('\n');
			return;
		}

		for (int i = at; i <= n; i++) {
			arr[depth] = i;
			dfs(i + 1, depth + 1);
		}
	}
}