백준 부등호 문제 (Java 구현)

이 문제는 DFS와 Backtracking을 구현하면 풀 수 있는 문제이다.

이러한 아이디어는 부등호라는 조건에 따라 값이 바뀔 수 있다는 점과, 선택된 숫자는 모두 달라야 한다는 부분에서 얻게 되었다. 조건에 부합하여 완성된 숫자들은 차례대로 ArrayList 배열에 들어가게 되고, 백트래킹을 이용했기에 방문되지 않은 숫자로 처음부터 다시 활용할 수 있다.

 

class Main {

static ArrayList<String> abc = new ArrayList<>();  //  완성된 숫자를 담을 공간

static boolean checked = new boolean[10]; // 방문 여부

static String str; // 추가될 문자

static String [] map; // 부등호를 담을 문자열 배열

static int k;

 

main 함수

{

Scanner sc = new Scanner(System.in);

k = sc.nextInt();

for(int i =0 ;i <k; i++) {

map[i] = sc.next();

}

 

for(int i =0; i<=9; i++) {

checked[i] = true;

dfs(i, 0, i+ "");  // 0부터 9까지의 문자

}

 

 

}

static void dfs(int i, int cnt, String str)

{

if(cnt==k) {

abc.add(str);  // 완성된 문자를 abc에 저장.

}else {

for(int j=0; j<=9; j++) {

if(!checked)

{

if(map[cnt].equals(">"))

{

if(i <=j)

{

continue;  // 계속 j를 증가시킨 후 백트래킹으로 or 그냥 방문

  }

}else

{

if(i>=j)   // j증가 후 방문 or 그냥 방문

{

continue;

  }

}

visited[j] = true;

dfs(j, cnt+1, str+j);

}

 

}

 

}

visited[i] = false; //백트래킹

 

}

 

}