바킹독 0x0B 강 - 백트래킹

JUN·2024년 7월 8일

바킹독 백트래킹 코딩 테스트

codingTest

목록 보기

20/23

📚 백트래킹이란?

현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘.

문제 유형

완전탐색 유형의 문제들의 최적화 버전이 백트래킹 문제.

그렇기에 완전탐색과 같은 유형에서 사용 가능.

“조건이 존재하는” 부분집합 생성 문제
“조건이 존재하는” 순열과 조합 생성 문제
“조건이 존재하는” 격자 탐색 문제

구현 예시

📝 문제 1. N과 M (1) (백준 15649)

링크 : https://school.programmers.co.kr/learn/courses/30/lessons/68936

문제 설명

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
- 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
- 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
- 수열은 사전 순으로 증가하는 순서로 출력해야 한다.

문제 풀이

순열을 구하라는 문제이다…간단하게 8중 포문(?)을 사용하면 구현 할 수 있다.

하지만 백트래킹을 이용한다면 그러지 않아도 풀 수 있다.

// N과 M 15649

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

public class boj_15649 {

  static int n; // 1~n 까지의 자연수
  static int m; // 길이가 m 인 수열의 길이
  static int[] arr;
  static boolean[] isUsed;

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

    arr = new int[10];
    isUsed = new boolean[10];

    // input
    n = Integer.parseInt(st.nextToken());
    m = Integer.parseInt(st.nextToken());

    recur(0);

    br.close();
  }

  public static void recur(int k) {
    // 만약 k == m 이면 여태까지 넣은 배열 요소 출력.
    if (k == m) {
      for (int i = 0; i < m; i++) {
        System.out.print(arr[i] + " ");
      }
      System.out.println();
    }
    // 배열에 들어갈 숫자가 1~n 까지니까 범위는 1 <= i <= n
    for (int i = 1; i <= n; i++) {
      if (!isUsed[i]) { // 만약 flag가 false면
        arr[k] = i; // arr 에 값 할당
        isUsed[i] = true; // true 로 바꿔주기
        recur(k + 1); // k에 1을 더한 후 재귀 호출
        isUsed[i] = false; // 조건에 맞는 수를 출력했다는 뜻이므로 해당 i는 false로 다시 바꿔줌.
      }
    }
  }
}

📝 문제 2. N과 M (2) (백준 15650)

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

문제 설명

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
- 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
- 고른 수열은 오름차순이어야 한다.

문제 풀이

첫번째 문제에서 오름차순이어야한다는 조건이 추가되었다.

첫번째 문제를 보면 arr에서 값을 할당할 때에 for문에 의해 할당된다는 것을 알 수 있다.

그러므로 해당 for문의 시작 부분을 트래킹하는 인수를 지정해주면 된다.

(내림차순일 경우 for문의 조건문 부분의 값을 인수로 지정해야할듯? )

package 백트래킹;

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

public class boj_15650 {
  static int n; // 1~n 까지의 자연수
  static int m; // 길이가 m 인 수열의 길이
  static int[] arr;
  static boolean[] isUsed;

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
		
		// input
    n = Integer.parseInt(st.nextToken());
    m = Integer.parseInt(st.nextToken());

    arr = new int[m];
    isUsed = new boolean[n + 1];

    recur(0, 1);

    br.close();
  }

  public static void recur(int k, int start) {
    // 만약 k == m 이면 여태까지 넣은 배열 요소 출력.
    if (k == m) {
      for (int i = 0; i < m; i++) {
        System.out.print(arr[i] + " ");
      }
      System.out.println();
      return;
    }
		
		// 배열에 들어갈 숫자는 낮아질 수 없으니 start를 따로 받아서 해당 수부터 arr[k]에 할당시킨다.
    for (int i = start; i <= n; i++) {
      if (!isUsed[i]) { // 만약 flag가 false면
        arr[k] = i; // arr 에 값 할당
        isUsed[i] = true; // true 로 바꿔주기
        recur(k + 1); // k에 1을 더한 후 재귀 호출
        isUsed[i] = false; // 조건에 맞는 수를 출력했다는 뜻이므로 해당 i는 false로 다시 바꿔줌.
      }
    }
  }
}