[Java] 재귀 함수 활용하기 - 백준 N과 M (1), (2), (9)

N과 M문제들

• 재귀 함수에서 여러 번의 호출마다 사용하는 변수들은 클래스 안에서 static으로 선언한다.
• 중복된 값을 체크하는 변수는 그 초기화 시점이 중요하다.
• 하나의 재귀 함수 호출에서 다음 재귀 함수 호출 전후로 중복 체크 변수를 flag로 활용한다.
• 현재 호출보다 깊은 호출에는 현재 호출에서 선택한 원소를 선택지에서 지우고, 현재 호출과 같은 깊이의 호출에는 현재 호출에서 선택한 원소를 선택할 수 있도록 한다.
• String을 매번 생성해 순열을 완성했을 때마다 System.out.println()으로 출력하는 것이 매우 비효율적이었다. 순열을 구성하는 원소들을 정적 변수 리스트에 저장해두고, 가장 깊은 재귀 호출 시에 리스트의 값들을 StringBuilder에 append해준 후 리스트를 초기화해준다. 그리고 모든 재귀함수 호출이 끝난 후에는 sb를 출력한다.

백준 15663번_ N과 M (9)

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
N개의 자연수 중에서 M개를 고른 수열
**입력**
첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.
**출력**
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.
예제 입력 1 
3 1
4 4 2
예제 출력 1 
2
4
예제 입력 2 
4 2
9 7 9 1
예제 출력 2 
1 7
1 9
7 1
7 9
9 1
9 7
9 9
예제 입력 3 
4 4
1 1 1 1
예제 출력 3 
1 1 1 1

위 문제에서는 순열끼리의 중복을 한 번 더 체크해야 했다.
N과 M 문제들 1번과 2번에서는 숫자끼리의 중복을 한 번 체크한 후에는 숫자들이 오름차순으로 순차적으로 선택되므로 순열이 중복되지 않는다. 하지만 위 문제에서는 숫자값이 아닌 각 숫자의 저장 위치의 중복을 확인해야 했고, 순열의 중복이 보장되지 않았기 때문에 가장 깊은 재귀 호출 시에 저장된 숫자 리스트의 값이 달라진다.

풀이 방향

• 가장 깊은 재귀 함수 호출 시 완성된 순열을 Set<String>에 넣어서 바로바로 중복된 순열을 제거하고, List로 변환해 sort해준 후 출력하는 방식으로 풀이했다. 하지만 이 경우 문제가 있다. 마지막 sort 과정에서 String 값으로 두 원소를 비교하는데, 순열의 숫자가 10 이상일 때는, String에서는 (숫자 하나씩 정렬하기 때문에) 정확한 정렬이 되지 않는다. 그러므로, 다음과 같이 바꾸어 풀이했다.

• 입력받은 순열을 구성하는 숫자들을 미리 정렬한다.
• 가장 깊은 재귀 함수 호출 시 완성된 순열을 List<int[]>에 넣어 순서를 유지한다.
• List를 순회하면서 바로 직전의 값과 현재 값을 비교해 다를 때만 현재 값을 StringBuilder에 추가한다.
  이때 Arrays.equals(a1, a2)를 사용할 수 있다.

N과 M (1), (2), (9) 풀이

백준 15649번_ N과 M (1)

import java.util.*;
import java.io.*;
public class Main {

    static int n;
    static int m;
    static boolean[] visited;
    static int[] seq;
    static StringBuilder allSeq;
    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());
        visited = new boolean[n + 1];
        seq = new int[m];
        allSeq = new StringBuilder();
        int depth = 0;
        for (int i = 1; i <= n; i ++) {
            visited[i] = true;
            seq[depth] = i;
            recur_f(depth + 1);
            visited[i] = false;
        }
        System.out.println(allSeq);
    }
    public static void recur_f(int depth) {
        if(depth == m) {
            for (int s : seq) {
                allSeq.append(s).append(" ");
            }
            allSeq.append("\n");
            return;
        }
        for (int i = 1; i <= n; i ++) {
            if (!visited[i]) {
                visited[i] = true;
                seq[depth] = i;
                recur_f(depth + 1);
                visited[i] = false;
            }
        }
    }
}

백준 15650번_ N과 M (2)

import java.util.StringTokenizer;
import java.io.*;
public class Main {

  static int n;
  static int m;
  static boolean[] visited;
  static int[] seq;
  static StringBuilder allSeq;
  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());
      visited = new boolean[n + 1];
      seq = new int[m];
      allSeq = new StringBuilder();
      int depth = 0;
      for (int i = 1; i <= n; i ++) {
          visited[i] = true;
          seq[depth] = i;
          recur_f(i, depth + 1);
          visited[i] = false;
      }
      System.out.print(allSeq);
  }
  public static void recur_f(int i, int depth) {
      if(depth == m) {
          for (int s : seq) {
              allSeq.append(s).append(" ");
          }
          allSeq.append("\n");
          return;
      }
      for (int j = i + 1; j <= n; j ++) {
          if (!visited[j]) {
              visited[j] = true;
              seq[depth] = j;
              recur_f(j, depth + 1);
              visited[j] = false;
          }
      }
  }
}

백준 15663번_ N과 M (9)

 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
import java.io.*;

//3일차_#8: 15663_N과 M (9)
public class Main {
    static int n;
    static int m;
    static int[] nums;
    static boolean[] visited;
    static List<int[]> seqList;
    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());
        nums = new int[n];
        visited = new boolean[n];
        seqList = new ArrayList<>();
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i ++) {
            nums[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(nums);
        int depth = 0;
        for (int i = 0; i < n; i ++) {
            int k = nums[i];
            visited[i] = true;
            int[] seq = new int[m];
            seq[depth] = k;
            recur_f(seq, depth + 1);
            visited[i] = false;
        }
        StringBuilder sb = new StringBuilder();
        int[] prevSeq = seqList.get(0);
        for (int s : prevSeq) {
            sb.append(s).append(" ");
        }
        sb.append("\n");
        for (int k = 1; k < seqList.size(); k ++) {
            int[] sortedSeq = seqList.get(k);
            if (!Arrays.equals(prevSeq, sortedSeq)) {
                for (int s : sortedSeq) {
                    sb.append(s).append(" ");
                }
                sb.append("\n");
                prevSeq = sortedSeq;
            }
        }
        System.out.print(sb);
    }
    public static void recur_f(int[] prev_seq, int depth) {
        if(depth == m) {
            seqList.add(prev_seq);
            return;
        }
        for (int i = 0; i < n; i ++) {
            if (!visited[i]) {
                int[] seq = Arrays.copyOf(prev_seq, prev_seq.length);
                int k = nums[i];
                visited[i] = true;
                seq[depth] = k;
                recur_f(seq,depth + 1);
                visited[i] = false;
            }
        }
    }
}