[Algorithm] 99클럽 코테 스터디 13일차 TIL BOJ 2529

문제

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

풀이

문제 분석

• 부등호의 앞 뒤 숫자를 통해 식이 유효한지 검사하며 dfs를 진행하도록 문제를 해결했다
• 탐색 과정에서 숫자의 조합을 저장하기 위해 numbers 배열에 숫자를 순서대로 저장했다
• 또한 마지막 K개의 부등호까지 만족할 때에만 numbers에 저장된 숫자를 문자열로 변환하여 max & min과 값을 업데이트 했다

코드

import java.io.*;
import java.util.*;

public class Main {
    private static int K = 0;
    private static int[] numbers;
    private static char[] sign;
    private static boolean[] visited;
    private static String max = "";
    private static String min = "9999999999";
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        K = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        numbers = new int[K+1];
        sign = new char[K];
        visited = new boolean[10];

        for(int i=0; i<K; i++) {
            sign[i] = st.nextToken().charAt(0);
        }

        for(int i=0 ; i<10 ; i++) {
            numbers[0] = i;
            visited[i] = true;
            dfs(i, 0);
            visited = new boolean[10];
        }



        bw.write(max+"\n");
        bw.write(min);
        bw.flush();
        bw.close();
    }

    private static void dfs(int i, int signIdx) {
        if(signIdx==K) {
            StringBuilder sb = new StringBuilder();
            for (int num : numbers) {
                sb.append(num);
            }
            String numStr = sb.toString();
            if (numStr.compareTo(max) > 0) {
                max = numStr;
            }
            if (numStr.compareTo(min) < 0) {
                min = numStr;
            }
            return;
        }

        for(int j=0 ; j<10 ; j++) {
            if(!visited[j] && checkStatement(i, j, signIdx)) {
                numbers[signIdx+1]= j;
                visited[j] = true;
                dfs(j, signIdx+1);
                visited[j] = false;
            }
        }
    }

    private static boolean checkStatement(int a, int b, int signIdx) {
        if(sign[signIdx] == '<') {
            return a<b;
        }
        return a>b;
    }
}

TIL

문제를 해결하고 다른 분들의 풀이를 찾아보았을 때 이 문제의 key-point는 백트래킹이라고 한다

• 백트래킹(backtracking): 해를 찾는 도중 해가 아니어서 막히면 뒤로 되돌아가 다시 해를 찾는 기법이다
• 모든 경우의 수를 전부 고려하는 알고리즘으로써 상태 공간을 트리로 나타낼 수 있을 때 적합한 방식이다
  
• dfs라고 생각했던 로직에서 사실 checkStatement를 통해 해를 만족하는지 검사하고 있으므로 나도 모르게 백트래킹을 사용하고 있었던 것이었다..!