[BOJ - JAVA] 2529 - 부등호(bfs, 브루트포스)

# 주소

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

2529번: 부등호

# 문제

 

# 문제 해설 및 코드 리뷰

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Main{

	static boolean[] check = new boolean[10]; // 0~9까지 check
	static int n;
	static char[] a = new char[10]; // 부등호는 최대 9개임
	static ArrayList ans = new ArrayList<>();

	static boolean ck(char a, char b, char c) {
		if (c == '<') {
			if (a > b) {
				return false;
			}
		}
		if (c == '>') {
			if (a < b) {
				return false;
			}
		}
		return true;
	}

	static void bfs(int index, String num) {
		if (index == n + 1) {
			ans.add(num);
			return;
		}

		for (int i = 0; i <= 9; i++) {
			if (check[i])
				continue;
			if (index == 0 || ck(num.charAt(index - 1), (char) (i + '0'), a[index - 1])) {
				check[i] = true;
				bfs(index + 1, num + Integer.toString(i));
				check[i] = false;
			}
		}

	}

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();

		for (int i = 0; i < n; i++) {
			a[i] = sc.next().toCharArray()[0];
		}

		bfs(0, "");
		Collections.sort(ans);

		System.out.println(ans.get(ans.size() - 1));
		System.out.println(ans.get(0));

	}

}

어려웠습니다.. 쉽다고 하는 분들도 계셨는데 전 어려웠어요

백트래킹하는건 똑같고 지금까지 해온 것과 별 다를것이 없지만 문자열을 받아서 풀이를 하는게 너무 어색했습니다.

아직 문자열을 다루는 것이 익숙하지 않아서 그런 것 같습니다. 더 공부해야겠네요!

 

여느 다른 백트래킹 문제처럼 일단 boolean 타입의 check와 정수 n, char 타입의 배열 a를 선언합니다.

ArrayList도 같이 선언하겠습니다. ArrayList를 선언하는 이유는 총 인덱스가 얼마인지 모르므로(가변적이므로)

최대값과 최소값을 구하는 데에 용이하기 때문입니다.

 

먼저, boolean타입의 ck함수와 return형식을 반환하는 bfs를 각각 선언합니다. ck함수는 특정 부등호의 방향에 따라 만약 오른쪽을 향하고 있는데 왼쪽이 크면 false, 왼쪽을 향하고 있는데 오른쪽이 크면 false를 반환하고 둘 다 아닐 경우 true를 반환하는 함수입니다. 

그리고 bfs를 정의하는데, 이때는 int타입의 index와 String타입의 num의 인자를 가집니다.

그리고 백트래킹 문제이므로 index 가 n + 1이 될 때마다 ans에 값을 저장하겠습니다. 이때 ans 는 ArrayList이므로 add메소드를 사용해야 하고 index가 n+1이 되어야 하는 이유는 부등호의 개수보다 정수의 개수가 한 개 더 많아야 하기 때문입니다!

그리고 index != n+1일때에는 for문을 사용하여 본격적으로 백트래킹을 실시합니다.

여기서 만약 방문한 index라면 continue를 하여 다음 for문으로 넘어가고 방문하지 않은 곳이라면 index 가 0이 아닐 때 ck함수를 실행합니다. 이 때, ck함수를 실행하는데, i+'0'(이렇게 쓰면 문자를 뜻합니다. 즉, num.charAt(index - 1)과 i + '0'을 비교하여 ck에서 참이라면 check[i] = true로 바꾸고 bfs의 index를 더하고 num의 i를 문자열로 바꿉니다.

이런식으로 계속해서 백트래킹이 일어나게 되고 무수히 많은 순열의 ArrayList들이 ans에 저장됩니다.

 

그리고 main함수를 실행합니다.

여기서부턴 평범하게 Scanner를 이용하여 n을 입력받고 a배열도 입력받습니다.

a의 원소는 문자이기 때문에 sc.next()를 썼고 입력받은 것의 각각 첫 번째는 배열에 넣기 위해 toCharArray를 썼습니다.

 

그리고 bfs를 실행하고 

정리된 ans를 오름차순으로 정렬하는데 ArrayList는 Collections.sort를 이용하여 정렬할 수 있습니다.

그리고 ans의 최대값과 최소값을 출력합니다. 최대값은 ans.size() - 1이 최대값이고 ans.get(0)하면 가장 앞의 순열을 꺼낼 수 있습니다.

 

감사합니다.