Baekjoon[JAVA] - 2529번 부등호(백트래킹)

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

2529번: 부등호

---

문제

두 종류의 부등호 기호 ‘<’와 ‘>’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제시된 부등호 순서열 A가 다음과 같다고 하자. 

A ⇒ < < < > < < > < >

부등호 기호 앞뒤에 넣을 수 있는 숫자는 0부터 9까지의 정수이며 선택된 숫자는 모두 달라야 한다. 아래는 부등호 순서열 A를 만족시키는 한 예이다. 

3 < 4 < 5 < 6 > 1 < 2 < 8 > 7 < 9 > 0

이 상황에서 부등호 기호를 제거한 뒤, 숫자를 모두 붙이면 하나의 수를 만들 수 있는데 이 수를 주어진 부등호 관계를 만족시키는 정수라고 한다. 그런데 주어진 부등호 관계를 만족하는 정수는 하나 이상 존재한다. 예를 들어 3456128790 뿐만 아니라 5689023174도 아래와 같이 부등호 관계 A를 만족시킨다. 

5 < 6 < 8 < 9 > 0 < 2 < 3 > 1 < 7 > 4

여러분은 제시된 k개의 부등호 순서를 만족하는 (k+1)자리의 정수 중에서 최댓값과 최솟값을 찾아야 한다. 앞서 설명한 대로 각 부등호의 앞뒤에 들어가는 숫자는 { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }중에서 선택해야 하며 선택된 숫자는 모두 달라야 한다. 

입력

첫 줄에 부등호 문자의 개수를 나타내는 정수 k가 주어진다. 그 다음 줄에는 k개의 부등호 기호가 하나의 공백을 두고 한 줄에 모두 제시된다. k의 범위는 2 ≤ k ≤ 9 이다. 

출력

여러분은 제시된 부등호 관계를 만족하는 k+1 자리의 최대, 최소 정수를 첫째 줄과 둘째 줄에 각각 출력해야 한다. 단 아래 예(1)과 같이 첫 자리가 0인 경우도 정수에 포함되어야 한다. 모든 입력에 답은 항상 존재하며 출력 정수는 하나의 문자열이 되도록 해야 한다. 

예제 입력 1 

2
< >

예제 출력 1 

897
021

예제 입력 2 

9
> < < < > > > < <

예제 출력 2 

9567843012
1023765489

---

풀이

2 ≤ k ≤ 9의 k로 부등호의 개수를 입력받고, 각각의 부등호까지 입력받은 후

0 ~ 9의 숫자로 중복없이 부등호를 만족하도록 나열하는 문제이다.

 

먼저 main 메소드이다.

void main

public static void main(String args[]) {
  Scanner sc = new Scanner(System.in);

  k = sc.nextInt();
  visited = new boolean[10];
  str = new String[k];

  for (int i = 0; i < k; i++) {
    str[i] = sc.next();
  }
  sc.close();

  // 최댓값 백트래킹
  bt("", 0, true);

  // 최댓값 백트래킹
  bt("", 0, false);

  // sort ans
  Collections.sort(ans);

  // print ans
  System.out.println(ans.get(ans.size() - 1));
  System.out.println(ans.get(0));
}

 

가장 먼저 부등호의 개수를 입력받고, 부등호까지 입력받은 후

백트래킹을 통해 부등호를 만족하는 모든 경우의 중복없는 수의 나열을 구한 후,

정렬을 통해 최댓값과 최솟값을 출력하도록 하였다.

 

 

이번 문제를 풀면서 백트래킹과 DFS의 차이에 대해 공부하는 시간을 가지게 되었다.

백트래킹과 DFS의 차이

우선 백트래킹과 DFS는 종종 함께 사용되는 기법이며 엄연히 다른 알고리즘 기법이다.

 

차이를 최대로(DFS)

위 글에 나왔던 DFS 개념을 다시 한번 살펴보면

하나의 길을 완벽하게 탐색한 후, 다른 길을 탐색하는 방식이었다.

 

방금 표현했듯이 DFS는 완벽하게 탐색한 후에 다른 길을 탐색한다면

백트래킹(Back-Tracking)은 하나의 길을 탐색하다가

"아, 여기선 해가 안 나올 것 같다"와 같은 조건이 있다면

끝까지 탐색하지 않고 다른 길로 넘어가는 것이다.

 

정리하자면 아래와 같다.

• DFS - 모든 노드를 방문하되, 깊이를 우선으로 탐색한다.
• 백트래킹 - 탐색을 진행하다가 해가 나오지 않는 경우를 만나면 탐색을 멈추고 다른 경우를 탐색한다.

 

그래서 이번 문제는 기본적으로 DFS 기법을 사용하면서,
조건을 추가해 불필요한 탐색은 하지 않도록 하는 백트래킹 기법도 함께 사용해보도록 할 것이다.

 

void bt ( DFS 기법만 사용하는 경우 )

public static void dfs(String result, int depth) {
  if (depth == k + 1) { // 끝까지 탐색했을 때
    ans.add(result);
  } else {
    for (int i = 0; i < 10; i++) { // 0 ~ 9까지 탐색
      if (!visited[i]) { // 방문하지 않았을 때
        /**
         * 첫번째 숫자는 비교할 값이 없으므로 바로 넣고,
         * 두번째 숫자부터는 이전 숫자와 비교하여 부등호를 만족하는지 확인한다.
         */
        if (depth == 0 || compare(result.charAt(result.length() - 1) - '0', i, str[depth - 1])) {
          visited[i] = true; // 방문 표시
          bt(result + i, depth + 1); // 다음 depth로 이동
          visited[i] = false; // 방문 표시 해제
        }
      }
    }
  }
}

위 메서드는 기본적으로 depth 값 0을 시작으로

입력받은 부등호 개수 + 1의 깊이(필요한 숫자의 개수)만큼까지 탐색하는 방식으로,

전형적인 DFS의 형태를 띄고 있다.

 

여기서 백트래킹의 개념을 적용해본다면, 아래와 같게 변한다.

void bt ( 조건 추가 )

public static void bt(String result, int depth, boolean isMax) {
  if (depth == k + 1) { // 끝까지 탐색했을 때
    ans.add(result);
  } else {
    int start = isMax ? 9 - k : 0;
    int end = isMax ? 10 : k + 1;
    for (int i = start; i < end; i++) { // 0 ~ 9까지 탐색
      if (!visited[i]) { // 방문하지 않았을 때
        /**
         * 첫번째 숫자는 비교할 값이 없으므로 바로 넣고,
         * 두번째 숫자부터는 이전 숫자와 비교하여 부등호를 만족하는지 확인한다.
         */
        if (depth == 0 || compare(result.charAt(result.length() - 1) - '0', i, str[depth - 1])) {
          visited[i] = true; // 방문 표시
          bt(result + i, depth + 1, isMax); // 다음 depth로 이동
          visited[i] = false; // 방문 표시 해제
        }
      }
    }
  }
}

이 문제는 어차피 부등호만 만족하면 되기 때문에

반드시 필요한 숫자의 개수만큼 순서대로 사용되게 된다.

중간에 건너뛰는 숫자가 없다는 뜻이다.

 

그래서

끝까지 탐색하여 부등호를 만족하는 모든 경우의 해를 구하지 않고,

필요한 숫자까지만 탐색하여 해를 구하도록 하였다.

 

이렇게 끝까지 탐색하지 않고 해가 나올 가능성이 있는 길만

탐색하고 넘어가는 알고리즘 기법을 백트래킹이라고 한다.

 

 

아래는 전체 코드이다.

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main {
  static List<String> ans = new ArrayList<String>();
  static int k;
  static boolean[] visited;
  static String[] str;

  public static void main(String args[]) {
    Scanner sc = new Scanner(System.in);

    k = sc.nextInt();
    visited = new boolean[10];
    str = new String[k];

    for (int i = 0; i < k; i++) {
      str[i] = sc.next();
    }
    sc.close();

    // 최댓값 백트래킹
    bt("", 0, true);

    // 최댓값 백트래킹
    bt("", 0, false);

    // sort ans
    Collections.sort(ans);

    // print ans
    System.out.println(ans.get(ans.size() - 1));
    System.out.println(ans.get(0));
  }

  /**
   * 백트래킹
   * 
   * @param result
   * @param depth
   */
  public static void bt(String result, int depth, boolean isMax) {
    if (depth == k + 1) { // 끝까지 탐색했을 때
      ans.add(result);
    } else {
      int start = isMax ? 9 - k : 0;
      int end = isMax ? 10 : k + 1;
      for (int i = start; i < end; i++) { // 0 ~ 9까지 탐색
        if (!visited[i]) { // 방문하지 않았을 때
          /**
           * 첫번째 숫자는 비교할 값이 없으므로 바로 넣고,
           * 두번째 숫자부터는 이전 숫자와 비교하여 부등호를 만족하는지 확인한다.
           */
          if (depth == 0 || compare(result.charAt(result.length() - 1) - '0', i, str[depth - 1])) {
            visited[i] = true; // 방문 표시
            bt(result + i, depth + 1, isMax); // 다음 depth로 이동
            visited[i] = false; // 방문 표시 해제
          }
        }
      }
    }
  }

  /**
   * 부등호를 만족하는지 확인하는 함수
   * 
   * @param num1
   * @param num2
   * @param str
   * @return 부등호를 만족하면 true, 아니면 false
   */
  public static boolean compare(int num1, int num2, String str) {
    if (str.equals("<")) {
      if (num1 < num2) {
        return true;
      }
    } else {
      if (num1 > num2) {
        return true;
      }
    }
    return false;
  }
}

성공^^