N과 M(1)

문제 정보

• 백준 실버 3
• 백트래킹, DFS
• 문제 링크

풀이

전형적인 [백트래킹] 문제.

가능한 모든 수열을 출력해야 하기 때문에 DFS를 통해 완전탐색 해야한다.

현재 뽑은 숫자의 개수를 기준으로, 덜 뽑았으면 하나 더 뽑고, $M$개를 뽑았으면 출력한다.

그리고 중복 없이 출력해야 하므로 visited[] 배열을 통해 중복을 방지한다.

• visited[i] == true: 이미 사용한 숫자이므로 스킵
• visited[i] == false: 사용 가능

또한 탐색 이후에는 visited[i]를 원래대로 되돌려야 한다. (visited[i] = false)

visited[i]는 현재 탐색 경로에서 $i$를 썼는지를 나타낸다. 원래대로 되돌리지 않는다면, 다음 탐색 경로까지 사용 흔적이 남아버리고, 이후 탐색이 제대로 이어지지 않게 된다.

• 예시($N=3$, $M=2$)
  • 원래대로 되돌리지 않는 경우
    • 1 2
    • 1 3
    • 출력 후 종료

코드

import java.io.*;
import java.util.*;
 
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());
        
        arr = new int[M];
        visited = new boolean[N + 1];
        
        dfs(0);
        
        System.out.println(sb);        
    }
    
    static void dfs(int depth) {
        if (depth == M) {
            for (int i = 0; i < M; i++)
                sb.append(arr[i]).append(' ');
            sb.append('\n');
            return;
        }
        
        for (int i = 1; i <= N; i++) {
            if (!visited[i]) {
                visited[i] = true;
                arr[depth] = i;
                dfs(depth+ 1);
                visited[i] = false; // 백트래킹 핵심
            }
        }
    }
}