백준의 N과 M (1) 문제다.
간단하게 문제를 정리하자면, 자연수 N과 M이 주어지는데, 숫자 1부터 N까지 중복 없는 M개의 요소를 가진 수열을 구하는 문제다.
N은 4이고, M은 3라는 가정 하에, 코드를 작성하기 이전 머릿속으로 한 번 어떻게 백트래킹으로 이 문제를 해결할 수 있을지 생각해보자.
고려해야 할 조건은 2개다.
1. 수열의 길이가 3을 넘지 않도록.
2. 배열 내의 중복인 숫자가 있는지.
첫번째 요소
수열의 첫 번째 요소로는 1~4까지 모두 가능하다
수열은 사전 순으로 증가하는 순서대로 출력해야 한다니 1을 선택하자
두 번째 요소
그럼 위의 사진고 같이 선택지가 생긴다. 사전 순대로 증가해야 하니 2를 선택하자.
3번째 요소
이제 3번째 요소까지 왔다. 수열을 구했으니 수열을 출력해주고, 다시 전 단계로 돌아가서 마지막 요소를 채우고 출력한다.
2번째 요소
3번째 요소
3번째 요소까지 모두 선택했으니 출력하고 전 단계로 돌아간다. 그다음 3번째 요소를 4로 선택한 뒤 출력한다.
이로서 1, 3, * 수열은 모두 구했다.
나머지 수열들도 이와 동일한 방법으로 계속 구하면 된다. 그럼 이제 코드를 짜 보자.
드
package baekjoon_java.SilverIII;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
/*https://www.acmicpc.net/problem/15649
백트래킹 , 23396KB ,268ms*/
public class N과M1 {
public static int[] arr;
public static boolean[] visit;
public static StringBuilder sb = new StringBuilder();
public static int N;
public static int M;
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];
visit = new boolean[N];
back(0);
System.out.println(sb);
}
public static void back(int depth) {
if (depth == M) { // 재귀 깊이가 M과 같아지면 탐색과정에서 담았던 배열을 출력
for (int val : arr) {
sb.append(val).append(' ');
}
sb.append('\n');
return;
}
for (int i = 0; i < N; i++) {
if (!visit[i]) { // 만약 해당 노드(값)을 방문하지 않았다면?
visit[i] = true; // 해당 노드를 방문상태로 변경
arr[depth] = i + 1; // 해당 깊이를 index로 하여 i + 1 값 저장
back(depth + 1); // 다음 자식 노드 방문을 위해 depth 1 증가시키면서 재귀호출
visit[i] = false; // 자식노드 방문이 끝나고 돌아오면 방문노드를 방문하지 않은 상태로 변경
}
}
}
}
문제에서 N과 M이 주어지고, 중복되는 수를 제외한 모든 경우의 수를 탐색하면 된다. 그럼 기본적으로 재귀를 통해 풀어볼 수가 있겠다.
이 때 재귀를 하면서 이미 방문한 노드(값)이라면 다음 노드를 탐색하도록 하기 위해(유망한 노드인지 검사하기 위해) N 크기의 boolean 배열 을 생성하고, 탐색과정에서 값을 담을 int 배열 arr 을 생성한다.
dfs 함수에는 N과 M을 변수로 받아야하는 건 당연지사, depth 변수
를 추가해야한다. depth를 통해 재귀가 깊어질 때마다 depth를 1씩 증가시켜 M과 같아지면 더이상 재귀를 호출하지 않고 탐색과정 중 값을 담았던 arr 배열을 출력해주고 return 하는 역할을 위해서다.
코드로 보면 아래와 같다.
일단 주석으로 설명을 했지만 다시 한번 설명하자면, 중복되는 수는 담을수 없기에 방문할 필요조차 없다. 즉, 방문 상태를 판단하기 위해 visit[] 배열이 있는 것이고, 해당 index가 방문하지 않는 노드(값)일 때만 재귀호출을 해주면 된다. 이게 백트래킹의 가장 기초라 할 수 있다.
