[Python/Java] 백준 2529 - 부등호 [DFS]

문제

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

 

해설

Brute Force로 접근하였는데 생각보다 풀어내기 쉽지 않았다.

 

이후 생각을 바꿔 DFS를 이용하였다. 뿐만 아니라 백트래킹(Backtracking)에 대한 이해도 필요하다. 탐색 도중 더 깊은 depth에 대한 탐색이 필요 없을 때 pruning이라 불리는 가지치기를 이용하여 유망한(promising) 경로만 계속 진행한다. 이 과정은 "선택 - 탐색 - 복구" 구조로 구성되어 있고, 이를 통해 가능한 모든 경우의 수를 탐색할 수 있다.

 

이 Backtracking은 마치 임계구역 문제에서 한 번에 한 경로만 특정 숫자를 사용할 수 있도록 보호하는 역할과 유사한데, 공유 메모리 문제에서 고려되는 Critical Section에 대한 Lock을 수행하는 아이디어가 떠오르지 않아 개인적으론 어려웠던 문제였다.

 

이 문제에선 Python이나 Java 모두 Single Thread 상태이므로 공유 변수에 대한 통제와 스케줄러 시퀀스는 고려하지 않아도 되지만 실무에선 어느 정도 통제가 필요할 수 있다.

 

Python

from sys import stdin


def is_valid(prev, current, sign):
    if sign == '<':
        return prev < current
    else:
        return prev > current


def dfs(depth: int, answer: list):
    if depth == n + 1:
        num_str = ''.join(map(str, answer))
        result.append(num_str)
        return

    for current in range(10):
        if not visited[current]:
            if depth == 0 or is_valid(answer[-1], current, signs[depth - 1]):
                visited[current] = True
                dfs(depth + 1, answer + [current])
                visited[current] = False	# Backtracking


n = int(stdin.readline())
signs = stdin.readline().strip().split(" ")
visited = [False for _ in range(10)]
result = []
dfs(0, [])
print(max(result))
print(min(result))

 

Java

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

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

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

        k = Integer.parseInt(br.readLine().trim());
        signs = br.readLine().split(" ");

        dfs(0, new ArrayList<>());

        Collections.sort(result);
        System.out.println(result.get(result.size() - 1)); 
        System.out.println(result.get(0)); 
    }

    public static void dfs(int depth, List<Integer> answer) {
        if(depth == (k + 1)) {
            StringBuilder numStr = new StringBuilder();
            for(int num : answer) {
                numStr.append(num);
            }
            result.add(numStr.toString());
            return;
        }

        for(int current=0; current<10; current++) {
            if(!visited[i]) {
                if(depth == 0 || isValid(answer.get(answer.size() - 1), current, signs[depth - 1])) {
                    visited[i] = true;
                    answer.add(i);
                    dfs(depth + 1, answer);
                    answer.remove(answer.size() - 1);
                    visited[i] = false;
                }
            }
        }
    }

    public static boolean isValid(int prev, int current, String sign) {
        if (sign.equals("<")) {
            return prev < current;
        } else {
            return prev > current;
        }
    }
}