(Baekjoon) GreedyAlgorithm - (12) 부등호

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

2529번: 부등호

이 문제를 풀기위해 선행되어야 하는 문제 : 로또, nqueen, dfs-bfs 

 

linked list, dfs, bfs, queue, stack 의 개념을 다시 한번 잡고왔다.

이 문제는 depth-First Search 를 이용하는 backtracking 문제를 사용하여서 풀었다.

백트래킹을 포함하여 개념과 코드를 이해하였다면 쉽게 풀수있다.(하지만 이해하는 과정이 나는 개인적으로 오래걸렸다)

 

0으로 시작하여서 dfs로 깊게 깊게 들어가며 만족하지 않는다면 dfs 수행을 포기하는식으로한다.

save[] 는 방문을 했는지 안했는 유무를 visited를 대신하기 위해 필요한것이고

list[] 는 모든 dfs탐색을 저장하였다.

아래와같은 dfs탐색후 list에 저장해서 나열해볼경우 오름차순으로 정리됨을 알게 되었으며

index : 0 , index : size of list - 1 : max 라는것을 알수있다.

 

count == k가 될경우 해당 노드는 통과된것이니 해당노드들의 줄기를 list에 추가하는식으로 진행하였다.

isPossible함수는 해당 노드가 정답에 반하는것인지 확인후 아니라면 제거해주는 역할을해준다.

 

 

package GreedyAlgorithm;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class _2529 {
    
    static int k;
    static String Inequality[];
    static StringBuffer st = new StringBuffer();
    static int save[] = new int[10];
    static List<String> list = new ArrayList<String>();

    public static void dfs(int start,int count,String dap){
        if(count == k)
            list.add(dap);
        else{
            for (int i = 0; i < 10; i++) {
                if(isPossible(Inequality[count],start,i,count)){
                    // System.out.println(dap + Inequality[count] + i);
                    save[count+1] = i;
                    dfs(i,count+1,dap + i);
                }
                
            }
        }


    }

    public static boolean isPossible(String c,int a,int b,int count){ 
        for (int i = 0; i <= count; i++) {
            if(save[i] == b)
                return false;
        }                    // 이미 한숫자라면
        if(c.equals("<")){ // 비교하기
            if( b < a)
                return false;
        }
        else{
            if( a < b)
                return false;
        }
        return true;


    }

    


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        k = Integer.parseInt(br.readLine());
        Inequality = br.readLine().split(" ");

        for (int i = 0; i < 10; i++) {
            save[0] = i;
            dfs(i,0,i+"");
        }
        System.out.println(list.get(list.size()-1) + "\n" + list.get(0));

    }
    
    
}

 

 

 

 

 

 

 

 

백준문제풀이Github : 

https://github.com/sdk0213/baekjoon-study

sdk0213/baekjoon-study