사실 처음에 이 문제를 접하고 브루트포스처럼 모든 경우의 수를 구해볼까 싶었지만 그렇게 풀라고 주는 문제는 아닌 것 같았다. 애초에 백트래킹에 속한 문제로 이미 백트래킹을 이용해야한다는 것도 알고 있었고.
아무튼 코드를 작성하다가 영 코드 작성 진도가 안 나가서 몇 가지 아이디어를 더 고민해보다 결국 서칭을 해서 힌트를 얻었다.
알게 된 점은 일단 백트래킹은 유망성을 판단하여 될 것 같은 놈인지 본다는 것이었다.
그리고 의외였던 건 백트래킹에서 사용되는 대표적인 알고리즘이 DFS라는 것이다.
백트래킹을 푸는 방법 중 하나가 DFS라는 것이다. BFS로 풀 수 있는 문제도 있는 것 같다. 아무튼 최근 학습한 DFS를 적용하여 문제 풀이를 시작하였다.
DFS는 재귀를 이용한 구현이 흔하니까 뭔가 풀다보면 머리가 복잡해지는 것 같다.
그림판으로 그려서 내가 어디까지 했는 지 그려가면서 푸는 중이다.
핵심
핵심은 1~4까지 반복문을 돌면서 접근을 하는데
당연히 방문한 녀석은 표시를 해주고 조합들을 저장해주기 위해서 ary에 저장도 하고
그 후 DFS를 재귀적으로 호출을 하는데
만약 원하는 길이의 구성이 나오면 리턴하고 나와서 이미 진행한 숫자는 visited에서 지워주는 것이다!
이렇게 하는 이유는 다음 반복문에서 숫자들을 새롭게 접근하기 위함이다
dfs(0) -> dfs(1) => ary[1,0]
0는 안되고 1해서 넣기 => ary[1,2] 완성 후 리턴
2는 방문하지 않은 것으로 다시 변경하고
0,1 안되고 2해서 넣기 => ary[1,3] 완성 후 리턴
3는 방문하지 않은 것으로 다시 변경하고
0,1,2 안되고 3해서 넣기 => ary[1,4] 완성 후 리턴
3는 방문하지 않은 것으로 다시 변경하고
반복문 종료 후 다시 dfs(0)에 자리로 이동!
0의 방문여부를 다시 취소하고 이제는 1부터 시작!성공 코드
import java.io.*;
import java.util.*;
public class Main {
static StringBuilder sb = new StringBuilder();
static boolean[] visted;
static int[] ary;
static int maxLength;
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());
visted = new boolean[N];
ary = new int[M];
maxLength = M;
DFS(0);
System.out.println(sb);
}
private static void DFS(int length) {
//채울 길이만큼 다 채웠으면
if(length == maxLength){
//지금까지 쌓은 값들 전부 출력
for (int val : ary) {
sb.append(val).append(" ");
}
sb.append("\n");
return;
}
//채울 길이 아직 못 채웠으면 더 넣어보자
for(int i = 0 ; i < visted.length; i++){
//아직 방문하지 않았다면 방문 체크하고 값 더 넣기
if(!visted[i]){
visted[i] = true;
ary[length] = i+1;
DFS(length+1);
visted[i] = false;
}
}
}
}