[JAVA] 백준 알고리즘 2529번 (부등호)

문제

---

이번에 다뤄볼 문제는 2529번 문제 '부등호'입니다.

문제에서 연습해야 하는 key-point는 백트래킹입니다.

 

백트래킹(backtracking)이란, 해를 찾는 도중 해가 아니어서 막히면 되돌아가서 다시 해를 찾아가는 기법을 말합니다. 모든 경우의 수를 전부 고려하는 알고리즘으로써 상태 공간을 트리로 나타낼 수 있을 때 적합한 방식입니다. 일종의 트리 탐색 알고리즘이라고 봐도 무방한데요. 방식에 따라서 깊이 우선 탐색(Depth First Search, DFS)과 너비 우선 탐색(Breadth First Search, BFS), 최선 우선 탐색(Best First Search/Heuristic Search)이 있습니다. 이번 문제에서처럼 모든 경우의 수를 고려하되 트리의 깊이가 정해져 있는 경우 DFS를 사용하는 것이 바람직합니다.

 

Backtracking

위 그림에서 실선은 탐색 방향, 점선은 백트래킹 방향을 나타낸다고 보시면 됩니다. A - B - D(트리의 마지막 포인트)까지 탐색을 마친 후 B로 백트래킹하여 이번엔 다른 경우의 수인 E를 탐색하러 갑니다. 이런 방식을 백트래킹이라 하며 오늘 문제에서는 이 개념을 사용해보려 합니다.

 

문제를 살펴보면 정답으로 선택된 숫자에 중복이 없어야 하며 최솟값과 최댓값을 구해내야 하는 문제입니다. 그런데 주어진 k값의 최대가 9이기 때문에 정답의 길이로 주어진 k+1의 값은 최대 10으로 고정됩니다.

따라서 우리는 이 문제를 DFS로 탐색하며 백트래킹을 활용하여 "모든 경우의 수"를 구해도 큰 무리가 없음을 알 수 있습니다.

 

이제는 0~9까지의 숫자 중 k+1 길이의 숫자 조합에 대한 모든 경우의 수를 0부터 순서대로 탐색하기만 하면 됩니다. 물론 탐색을 진행할 때 문제로 주어진 부등호 관계에 성립하는지를 체크하며 탐색해야 하며 이 탐색이 완료되었을 때 저장해놓은 k+1 자릿수의 모든 경우의 수 중 가장 마지막 값이 최댓값, 가장 처음 값이 최솟값이 됩니다.

 

아래 해답 코드를 보면 더 쉽게 이해할 수 있으실 겁니다.

---

코드(JAVA)

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

public class Main {

    static int k;
    static String[] signs;
    static boolean[] visited = new boolean[10]; // 0~9까지 숫자 방문체크용
    static List<String> numbers = new ArrayList<>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        k = sc.nextInt();
        signs = new String[k];
        for (int i = 0; i < k; i++) {
            signs[i] = sc.next();
        }

        // 부등호의 앞뒤에 들어가는 숫자는 {0,1,2,3,4,5,6,7,8,9}
        for (int i = 0; i <= 9; i++) {
            visited[i] = true;
            dfs(i, 0, i + "");
        }

        System.out.println(numbers.get(numbers.size() - 1));
        System.out.println(numbers.get(0));
    }

    private static void dfs(int number, int numberIndex, String str) {
        if (numberIndex == k) {
            numbers.add(str);
        } else {
            for (int i = 0; i <= 9; i++) {
                if (!visited[i]) {
                    if (signs[numberIndex].equals("<")) {
                        if (number >= i) {
                            continue;
                        }
                    } else {
                        if (number <= i) {
                            continue;
                        }
                    }
                    visited[i] = true;
                    dfs(i, numberIndex + 1, str + i);
                }
            }
        }
        visited[number] = false;
    }
}

 

2529번: 부등호