[자바] 백준 N과 M 시리즈(1~4) / 백트래킹

백트래킹 연습하기에 최고로 좋은 문제인 백준 문제 N과 M시리즈입니다.

 

백준 15649 : N과 M(1) 자바 풀이

https://www.acmicpc.net/problem/15649

15649번: N과 M (1)

package com.sosow0212.study;

import java.util.Scanner;

// https://www.acmicpc.net/problem/15649 (N과M (1))
public class q15649_1 {
    private static int n, m;
    private static int[] arr;
    private static boolean[] visited;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        arr = new int[m + 1];
        visited = new boolean[n + 1];
        recursion(0);
    }

    private static void recursion(int index) {
        if (index == m) {
            for (int i = 0; i < m; i++) {
                System.out.print(arr[i] + " ");
            }
            System.out.println();
            return;
        }

        for (int i = 1; i <= n; i++) {
            if (!visited[i]) {
                visited[i] = true;
                arr[index] = i;
                recursion(index + 1);
                visited[i] = false;
            }
        }
    }
}

자신과 다른 모든 수의 쌍을 구해야합니다.

따라서 dfs를 타고나서 visited[i]를 false 처리 해줍니다.

​

그렇게 된다면 예를들어 2번으로 넘어 갔다면, 1번이 다시 true인 상태가 되므로 arr에 추가될 수 있습니다.

​

 

백준 15650 : N과 M(2) 자바 풀이

https://www.acmicpc.net/problem/15650

15650번: N과 M (2)

package com.sosow0212.study;

import java.util.Scanner;

// https://www.acmicpc.net/problem/15650 (N과M (2))
public class q15650_2 {
    private static int n, m;
    private static int[] arr;
    private static boolean[] visited;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        arr = new int[m + 1];
        visited = new boolean[n + 1];
        recursion(0);
    }

    private static void recursion(int index) {
        if (index == m) {
            for (int i = 0; i < m; i++) {
                System.out.print(arr[i] + " ");
            }
            System.out.println();
            return;
        }

        for (int i = 1; i <= n; i++) {
            if (!visited[i]) {
                visited[i] = true;
                arr[index] = i;
                recursion(index + 1);
                for (int j = i + 1; j <= n; j++) {
                    visited[j] = false;
                }
            }
        }
    }
}

1번 문제와는 조금 다른 출력을 보입니다.

여기서의 출력은 기준이 되는 수보다 같거나 작은 수는 출력하면 안됩니다.

4,2 입력에서 기준이 2라면 [2 3], [2 4] 이렇게 되어야합니다.

​

그렇다면 '기준 수보다 작거나 같은 수'를 어떻게 걸러야할까요?

바로 재귀를 태운 후 for문을 통해 i보다 큰 수부터 false 처리를 해주면 됩니다.

​

그렇게 된다면 다음과 같은 순서로 작동합니다.

1. 기준 수 1이 처음 돈다면 1번의 모든 탐색을 수행합니다.
2. 기준 수1의 모든 탐색이 끝났다면 1이후부터의 수를 모두 false처리를 합니다.
3. 기준 수 2가 탐색을 시작합니다. 이때 2이후의 모든 수는 false이고, 1은 true 상태입니다.

이런식으로 자기 이전의 수를 모두 안나오게 처리할 수 있습니다.

 

 

백준 15651 : N과 M(3) 자바 풀이

https://www.acmicpc.net/problem/15651

15651번: N과 M (3)

package com.sosow0212.study;

import java.util.Scanner;

// https://www.acmicpc.net/problem/15651 (N과M (3))
public class q15651_3 {
    private static StringBuilder sb = new StringBuilder();
    private static int n, m;
    private static int[] arr;
    private static boolean[] visited;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        arr = new int[m + 1];
        visited = new boolean[n + 1];
        recursion(0);
        System.out.println(sb);
    }

    private static void recursion(int index) {
        if (index == m) {
            for (int i = 0; i < m; i++) {
                sb.append(arr[i] + " ");
            }
            sb.append("\n");
            return;
        }

        for (int i = 1; i <= n; i++) {
            arr[index] = i;
            recursion(index + 1);
        }
    }
}

이 문제는 1번과 조금은 유사한 출력 형태를 지닙니다.

예를들어 4 2가 입력이라면 '1 1 ~ 1 4', '2 1 ~ 2 4' 이런 식으로 자신을 포함한 모든 수의 쌍을 출력해야합니다

​

그렇다면 visited를 이용할 필요가 없어집니다.

바로 재귀를 태우면 모든 수의 쌍을 구할 수 있습니다.

​

StringBuilder() 메서드를 써야 시간초과가 나질 않습니다!

​

 

 

백준 15652 : N과 M(4) 자바 풀이

https://www.acmicpc.net/problem/15652

15652번: N과 M (4)

package com.sosow0212.study;

import java.util.Scanner;

// https://www.acmicpc.net/problem/15652 (N과M (4))
public class q15652_4 {
    private static int n, m;
    private static int[] arr;
    private static boolean[] visited;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        arr = new int[m + 1];
        visited = new boolean[n + 1];
        recursion(0);
    }

    private static void recursion(int index) {
        if (index == m) {
            for (int i = 0; i < m; i++) {
                System.out.print(arr[i] + " ");
            }
            System.out.println();
            return;
        }

        for (int i = 1; i <= n; i++) {
            if (index != 0 && arr[index - 1] > i) {
                continue;
            }
            arr[index] = i;
            recursion(index + 1);
        }
    }
}

이 문제의 출력은 다음과 같습니다.

기준 수와 동일하거나 큰 수를 쌍으로 갖습니다.

​

즉 기준 수보다 작은 수를 쌍으로 갖지 않습니다.

​

이렇게 풀기 위해서 recursion 즉 재귀를 태우기 전에 if문을 통해서 index가 0이 아닌 경우와 더불어 배열 arr[index - 1]의 값이 i보다 큰 경우 (이전 수보다 큰 경우)는 스킵을 해줍니다.

​

그리고 이것에 해당하지 않으면 값을 넣어주고 재귀를 태워주는 방식입니다.