Java

[백준 15649] N과 M (JAVA)

iheeeee6-6 2023. 5. 1. 22:44
728x90

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

 

15649번: N과 M (1)

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해

www.acmicpc.net

 

 

dfs를 사용하여 문제를 풀 수 있었다.

방문 여부를 확인하여 숫자를 뽑아서 배열에 넣고, m개를 뽑았을 경우에는 StringBuilder에 append한다!

 

 

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

public class Main {

	static int n, 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());
		visited = new boolean[n + 1];
		arr = new int[m];
		dfs(0);

		System.out.println(sb);
	}

	static void dfs(int depth) {
		if (depth == m) {
			for (int idx : arr)
				sb.append(idx).append(" ");
			sb.append("\n");
			return;
		}

		for (int i = 1; i < n + 1; i++) {
			if (!visited[i]) {
				visited[i] = true;
				arr[depth]=i;
				dfs(depth + 1);
				visited[i] = false;
			}
		}
	}

}

'Java' 카테고리의 다른 글

[백준 15663] N과 M (9) (JAVA)  (0) 2023.05.02
[백준 15657] N과 M(8) (JAVA)  (0) 2023.05.01
[백준 2668] 숫자고르기 (JAVA)  (0) 2023.04.30
[백준 4179] 불! (JAVA)  (0) 2023.04.29
[백준 2179] 비슷한 단어 (JAVA)  (0) 2023.04.28