안녕하세요. 오늘은 DFS/백트래킹을 이용하는 문제들을 풀어보려고 합니다.! 백준 15649. N과 M (1) 문제를 풀어보겠습니다.
https://www.acmicpc.net/problem/15649
1부터 N까지 자연수 중에서 중복 없이 M개를 골라야 합니다.
"중복 없이 M개를 고르는 것"이 문제의 키워드라고 판단했습니다. dfs로 1부터 N까지 모든 수를 탐색하되, visited 배열을 이용해서 이전에 탐색했는지 여부를 저장해주어야 합니다. 탐색한 값은 answer배열에 저장해줍니다.
핵심 로직은 다음과 같습니다.
boolean[] visited = new boolean[n+1];
int[] answer = new int [m];
//n = 탐색해야 할 자연수(1부터 n까지)
//m = 골라야 하는 숫자의 갯수
//idx = 현재까지 dfs함수를 탐색하면서 골라둔 숫자의 갯수
dfs(int n, int m, int idx) {
//dfs 탐색을 멈추는 로직
if(idx가 m과 같다면) { //dfs를 탐색하면서 고른 숫자 갯수가 m이라면
//answer 배열을 출력한 후 dfs 탐색을 멈춘다
return;
}
//dfs 탐색 로직
for(int i = 1; i <= n; i++) {
if(visited[i] == false) { //아직 i값을 탐색하지 않았다면
visited[i] = true; //i를 탐색한다
answer[idx] = i; //answer배열의 idx번째 값을 i로 저장
dfs(n, m, idx +1); //고른 숫자의 총 개수가 1 증가했으니까, idx를 1 증가시킨 후 dfs 재귀 돌린다
visited[i] = false; //dfs가 모든 경우의 수를 탐색해야하므로 해당 재귀함수가 완료된 후 탐색여부를 false로 바꾼다
}
}
}
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
visited = new boolean[n+1];
answer = new int[m];
sb = new StringBuilder();
dfs(n, m, 0);
System.out.println(sb.toString());
}
private static boolean[] visited;
private static int[] answer;
private static StringBuilder sb;
private static void dfs(int n, int m, int idx) {
if(idx == m) {
for(int num : answer) {
sb.append(num + " ");
}
sb.append("\n");
return;
}
for(int i = 1; i <= n; i++) {
if(visited[i] == false) {
visited[i] = true;
answer[idx] = i;
dfs(n, m, idx + 1);
visited[i] = false;
}
}
}
}
[참고한 곳]
https://st-lab.tistory.com/115