🟦/백준
[실버 3] N과 M (1)
진뚱이용
2023. 4. 10. 17:20
https://www.acmicpc.net/problem/15649
15649번: N과 M (1)
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해
www.acmicpc.net
저번 스터디 때 쫑나기전 마지막 문제 여서 풀었는데
다시 보니 모르겠다
백트래킹 = 전체 순회 dfs가 편함
bfs로는 트리의 깊이가 무한대 일 때 사용 한다
import java.io.*;
import java.util.*;
class Main {
static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int N, M;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
boolean[] visited = new boolean[N];
for(int i =0 ; i< N ; i ++)
dfs(N, M, visited, i);
}
public static void dfs(int N, int M, boolean[] visited, int index) {
if (visited[index] == true)
return;
visited[index] = true;
sb.append(index+1+" ");
if(sb.length() == 2*M){
System.out.println(sb);
sb.setLength(sb.length()-2);
visited[index]=false;
return;
}
for (int i = 0; i < N; i++)
dfs(N, M, visited, i);
sb.setLength(sb.length()-2);
visited[index]=false;
}
}