[BOJ] 백준 2529 부등호 - Java 풀이

최근에 백준을 풀던 중 꽤 흥미로운 문제를 발견했다.

 

시간이 오래걸리기도 했는데 과정에서 꽤 재미를 느꼈다. 또한 배울점이 많은 코드라는 생각이 들어서 첨부했다. 조금 어렵다는 생각이 들기도 했는데 문제 자체가 굉장히 흥미로워서 그냥 붙잡고 불었다.

 

원래 좀 어려운 문제를 만나면 약간의 스트레스가 생기기 마련인데 이 문제는 그냥 재밌는 문제다. 다른 분들도 이 문제는 꼭 답지 보지 말고 풀어봤으면 한다. 

 

백트래킹 문제인데 부루트포스도 같이 사용해서 풀 수 있는 문제이다. 

 

문제는 아래와 같다.

 

문제 링크: https://www.acmicpc.net/problem/2529 

 

 

자 간단하게 dfs 순회하면서 모든 가능한 경우의 대해서 돌아보면 된다. 

 

물론 백트래킹 특성에 따라서 특정 조건에 따라서 가지치기하는 조건도 중간에 넣어주면 된다. 

 

우선 작성한 코드를 살펴보면 아래와 같다.

 

개선할 여지가 많은 코드이지만 미리 첨부하고 점차 개선해가는 방식으로 작성할 예정이다. 

 

자 코드를 보자. 

 

package 문제풀이.BOJ.문자열.백트래킹;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.sql.SQLOutput;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.StringTokenizer;

/*
    1150 ~ 1244

    조금 까다로운 문제네용.
    흥미로운 부분들이 많은 문제다.

 */
public class boj_2529 {
    public static String[] signs;
    public static int n;
    public static boolean[] visited = new boolean[10];
    public static ArrayList<String> candidateList = new ArrayList<>();

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

        for(int i = 0; i < n; i++){
            signs[i] = st.nextToken();
        }

        for(int i = 0; i < 10; i++){
            dfs(i, 0, String.valueOf(i), 0);
        }

        Collections.sort(candidateList); // 정렬
        // System.out.println(Arrays.deepToString(candidateList.toArray()));
        System.out.println(candidateList.get(candidateList.size() - 1)); // 최대값
        System.out.println(candidateList.get(0));                        // 최소값
    }

    public static void dfs(int leftValue, int indexOfSign, String numberString, int count){
        if(indexOfSign == n - 1){
            for(int i = 0; i < 10; i++){
                if(signs[indexOfSign].equals(">")){
                    if(leftValue <= i){
                        continue;
                    }
                    if(numberString.contains(String.valueOf(i))){
                        continue;
                    }
                    candidateList.add(numberString + String.valueOf(i));
                }else if(signs[indexOfSign].equals("<")){
                    if(leftValue >= i){
                        continue;
                    }
                    if(numberString.contains(String.valueOf(i))){
                        continue;
                    }
                    candidateList.add(numberString + String.valueOf(i));
                }
            }
            return;
        }

        visited[leftValue] = true;
        for(int i = 0; i < 10; i++){
            if(visited[i]){ // 이미 방문한 곳은 pass
                continue;
            }
            if(signs[indexOfSign].equals(">")){
                if(leftValue <= i){
                    continue;
                }
            } else if(signs[indexOfSign].equals("<")){ // leftValue < i
                if(leftValue >= i){
                    continue;
                }
            }
            if(numberString.contains(String.valueOf(i))){ // 이미 사용한 요소라면 pass
                continue;
            }
            visited[i] = true;
            // System.out.printf("indexOfSign: %d, numberString: %s\n", indexOfSign, numberString);
            dfs(i, indexOfSign + 1, numberString + String.valueOf(i), count + 1);
            visited[i] = false;
        }
        visited[leftValue] = false; // <- 이 부분 false 로 체크해주지 않으면 결과값을 구할 수 없음.
        /*
            이 부분에서 false 로 체크하지 않으면 빠져나갈때 처음 진입할때 true 로 체크했던 visited[leftValue] 는 계속해서
            true 인 상태로 남는다. leftValue가 계속 true 로 막혀있으니 새롭게 순회할때 leftValue 가 계속 방문되어있다고 착각하여
            제대로된 순회를 하지 못하는 것이다.
         */
    }
}

 

코드를 간단하게 설명해보자면 아래와 같다. 

 

우선 입력을 받는다. 

 

이후에 dfs 를 loop 안에서 10번 돌게 된다. (10번 도는 이유는 0부터 9까지 돌기 위함인데 이건 문제의 조건이다.)

 

dfs 를 돌고 나서 candidateList 를 sort 해주고 있다. 

 

candidateList는 만들어진 결과물을 모두 저장하는 리스트라고 보면 된다. 

 

이 리스트를 정렬하는 이유는 이 문제에서 구하고자 하는 것이 MAX 값과 MIN 값이기 때문이다. 그리고 나서 candidateList 의 맨 마지막에 있는 요소인 최대값과 가장 첫번째 요소인 최소값을 출력해주면 된다. 

 

가장 중요한 부분인 dfs 함수를 살펴보자. 

 

첫번째 인자로 leftValue 를 받고 있다. 

leftValue 는 <와 > 의 비교에서 왼쪽에 위치하는 비교대상이라고 보면 된다. 2 < 3 이라는 비교에서 2가 leftValue에 해당한다고 보면 된다. 

 

두번째 인자인 indexOfSign 은 <, > 이 포함된 array에서의 index를 말한다. 메인 내에서 signs 라는 array가 사용되는 것을 확인할 수 있을 것이다. 해당 array 는 순서대로 입력받은 부등호가  > < > > < .... 와 같은 수서로 들어가있다. 

 

세번째 인자인 numberString 은 우리가 알아내야하는 숫자로 된 결과물이라고 보면 된다. 

 

마지막 인자인 count 는 지금은 쓰이지는 않는데 미처 없애지 못했다. (추후에 개선하면서 없애도록 하겠다. 왜 남겨둔거지?)

 

자 그렇다면 dfs 내부의 로직을 살펴보자. 

 

첫번째로 등장하는 조건문에서 indexOfSign이 n - 1 인지를 확인하고 있다. 즉 indexOfSign이 입력받은 부등호의 개수만큼

진행되었는지를 따지는 조건문이다. 

 

만약 참이라면 입력받은 모든 부등호의 마지막 요소를 살펴보고 있기 때문에 오른쪽에 존재하는 비교 대상인 right value 를 선정해야한다. 그래서 for문이 10번 도는 것을 확인할 수 있을 것이다. 물론 10번 돌면서도 부등호의 조건에 맞지 않는 요소들은 그냥 pass 하는 조건이 있다. 

 

또한 모든 요소들인 0 ~ 9 는 단 한번만 쓰여야한다는 조건이 있기 때문에 .contains 를 통해서 해당 요소가 이미 사용되었는지 체크하는 것을 확인할 수 있다. 

 

체크하고 난뒤 candidateList 에 numberString을 추가하는데 그냥 추가하는 것이 아니라 현재 살펴본 i 즉 for 루프에서 조건을 거치고 나서 살아남은 i 에 대해서 string으로 변환하여 concat 해주고 있다. 살아남았다는 것은 부등호 조건에도 맞고 사용한 적도 없는 숫자를 의미한다. 

 

이렇게 진행했다면 return 을 통해 빠져나간다.

 

왜 빠져나갈까? indexOfSign이 n - 1 과 같다고 했으므로 봐야하는 곳까지 다 봤기 때문이다. 그러니 return 을 해야 한다. 

 

위에서 언급한 조건문 아래에 존재하는 부분이 있다. visited[leftValue] = true 로 진행되는 부분인데 이 부분은 다른 DFS 방식과 거의 유사하다고 보면 된다. 

 

for loop이 10번 도는 것을 확인할 수 있고 방문했다면 pass 시키는 조건이 있다. 또한 마찬가지로 부등호의 경우에 따라

대소 비교를 체크하는 조건 문장이 있고 numberString에서 이미 포함하는 문자인지에 대한 체크도 존재한다. 

 

이후로 dfs를 한번 더 돌기 전에 방문 처리를 해주고 dfs 를 진행한다. 여기서 indexOfSign에 +1을 해준 뒤 전달해주는 것을 확인할 수 있다. 다음 부등호를 살펴봐야하니까 이렇게 처리하는거다. numberString에 String.valueOf(i)를 더해줘서 전달하는 것도 살펴볼 수 있다. 

 

여기서 중요한 것은 dfs 를 다 돌고 나오면 다시 해당 index 에 대해서 방문처리를 false 로 바꾼다는 점이다. 

 

왜 다시 false 로 바꿀까?

 

이게 백트래킹의 핵심이다. 살펴보고 싶은 곳까지 방문했다가 다시 돌아나오는데 돌아나왔다고 해서 내가 붙잡고 있던 판이 이전과는 다른 상태이면 안된다. 출발할때와 똑같은 상태로 돌아와야한다. 

 

즉 특정 board 과 되었든 방문을 기록한 팻말이 되었든 간에 뭐든지 상태를 기록하는 존재가 있다면 방문하고 나와서 돌아나왔는데 상태의 표기를 이전 상태로 바꿀 수 없다면 의미가 없다. 

 

그래서 여기서 방문처리를 false 로 바꾸어 주는 것이다. 방문하기 이전 상태로 돌려주는 거다. 

 

이후에 for 문을 돌고 나서도 마찬가지다. 

 

맨 마지막에서 leftValue를 false 로 만들어주는 부분이 있는데 이 부분은 왜 썼을까? (사실 이 부분때문에 10분을 삽질했다.) 이 leftValue에 대한 방문처리를 false 로 만들어주지 않으면 결과는 아무것도 나오지 않는다. 혹은 candidateList 가 아예 빈 리스트로 남게 된다. 

 

왜일까? 우리는 main에서 이미 for 루프를 10번 돌고 있었다. 즉 출발 지점을 세팅해주는 for 루프였고 이 for 루프도 마찬가지로 dfs 함수 내부로 들어가서 방문처리가 이루어진다. 

 

그런데 이 출발 지점에 대해서 방문 처리를 무효화시키지 않으면 우리는 매번 백트래킹할때마다 이전에 세팅한 출발 지점이 방문 체크된 상태로 진행하게 된다. 실제로는 백지화된 상태에서 매번 돌아야하는 데도 말이다. 

 

이 문제의 특성이 그러하다.

 

방문 가능한 모든 경우의 수를 돌아야하는 부루트포스의 성격을 띄고 있기 때문에 이렇게 풀 수 밖에 없다.