백준 - N과 M(1)_(15649)

⭐문제링크

문제 분류

백트래킹의 기본 문제이다. 왜 백트래킹인가?

1. 숫자는 중복되어선 안된다(가지치기 필요)
2. 일단 완전탐색으로 모든 수에 대해 접근하되, 1번의 조건이 만족된다면 해당 경우는 가지치기로 한다.

위 2가지가 백트래킹의 기본적인 판단요소이다.

백트래킹은 보통 재귀를 통해 풀어낸다.

📢백트래킹 vs 브루트포스 vs DFS

백트래킹은 이미 지나쳐온 곳을 다시 돌아가서 다른 가능성을 시도해보는 걸 반복하는 기법입니다. 반드시 DFS만으로 가능한 게 아니고 BFS 등으로도 가능하지만 일반적으로 DFS와 연관이 깊기는 합니다.

브루트 포스는 꼭 '깊이'나 '탐색'의 개념이 아니더라도, 모든 경우의 수를 다 대입해보는 것이면 브루트 포스입니다. 어떤 종류의 문제에서 어떤 방법을 쓰더라도요.

DFS는 여러 지점을 한 단계씩 거쳐가면서 탐색하고, 스택의 개념을 이용해서 이전 단계로 돌아가야만 DFS입니다.

🖥️코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int N;
    static int M;
    static int[] arr;
    static boolean[] visit;
    public static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        StringTokenizer st;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        arr = new int[M];
        visit = new boolean[N];

        dfs(N, M, 0);
        System.out.println(sb);
    }

    public static void dfs(int N, int M, int depth) {

        // 재귀 깊이가 M과 같아지면 탐색과정에서 담았던 배열을 출력
        if (depth == M) {
            for (int val : arr) {
                sb.append(val).append(' ');
            }
            sb.append('\n');
            return;
        }
        for (int i = 0; i < N; i++) {

            // 만약 해당 노드(값)을 방문하지 않았다면?
            if (visit[i] == false) {

                visit[i] = true;		// 해당 노드를 방문상태로 변경
                arr[depth] = i + 1;		// 해당 깊이를 index로 하여 i + 1 값 저장
                dfs(N, M, depth + 1);	// 다음 자식 노드 방문을 위해 depth 1 증가시키면서 재귀호출

                // 자식노드 방문이 끝나고 돌아오면 방문노드를 방문하지 않은 상태로 변경
                visit[i] = false;
            }
        }

    }
}