[코딩테스트] 브루트 포스(재귀-백트래킹)
reference : 2021 코딩테스트 기초(최백준) 강의를 공부하며 정리한 내용입니다.
- 백트래킹 알고리즘 : 브루트포스인데 더 이상 호출이 의미 없음을 발견했을 때 재귀 중단.
스타트와 링크(14889번)
https://www.acmicpc.net/problem/14889
문제
- N명을 N/2명씩 두 팀으로 나누려고 한다. (4 ≤ N ≤ 20, N은 짝수)
- 두 팀의 능력치를 구한 다음, 차이의 최소값을 구하는 문제
- S[ i ] [ j ] = i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치
- 팀의 능력치 : 팀에 속한 모든 쌍의 S[ i ] [ j ]의 합
입력
첫째 줄에 N(4 ≤ N ≤ 20, N은 짝수), 둘째 줄부터 N개의 줄에 S, 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100보다 작거나 같은 정수이다.
출력
첫째 줄에 스타트 팀과 링크 팀의 능력치의 차이의 최솟값을 출력한다.
풀이
- 각 사람(N명)이 어느 팀(2개)에 들어갈 건지 -> 2ⁿ가지 최대 2^20 = 1048576
- go(index, first, second) : 사람 번호, 1번 팀, 2번 팀
- 정답을 찾은 경우 index == n + 구성원 n/2인지 확인 + 최소값
- 다음 경우
- 1번 팀 or 2번 팀 go(index+1, first, second)
- 두 경우 모두 호출 전 first 또는 second에 index 넣고 호출 후 빼는 과정 필요
import java.util.*;
public class Main {
static int n;
static int[][] s;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
s = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
s[i][j] = sc.nextInt();
}
}
ArrayList<Integer> first = new ArrayList<>();
ArrayList<Integer> second = new ArrayList<>();
System.out.println(go(0,first,second));
}
private static int go(int index, ArrayList<Integer> first, ArrayList<Integer> second) {
if(index==n) {
//인원수 체크
if(first.size()!=n/2)
return -1;
if(second.size()!=n/2)
return -1;
int t1 = 0;
int t2 = 0;
for (int i = 0; i < n/2; i++) {
for (int j = 0; j < n/2; j++) {
if(i==j) continue;
t1 += s[first.get(i)][first.get(j)];
t2 += s[second.get(i)][second.get(j)];
}
}
int diff = Math.abs(t1-t2);
return diff;
}
int ans = -1;
first.add(index); //1번팀을 선택했으면 함수 호출 전 그 인덱스 사람을 넣어주기
int t1 = go(index+1,first,second);
if(ans==-1 || (t1!=-1&&ans>t1))
ans = t1;
first.remove(first.size()-1); //함수 호출이 끝나면 그 사람이 first 들어가 할 수 있는건 다 했으니 빼주기
second.add(index);
int t2 = go(index+1,first,second);
if(ans==-1 || (t2!=-1&&ans>t2))
ans = t2;
second.remove(second.size()-1);
return ans;
}
}
-> 최소값의 차가 t1, t2를 통해 ans에 저장되는 구조임. return diff를 통해 ans에 값이 저장되고 마지막엔 최소값이 리턴됨.
- 백트래킹은 아이디어가 중요함. N/2 넘는 경우 불가능하니까 이 경우 함수 중단해주는 코드를 추가해주기.
// 재귀 부르기 전에 추가 if(first.size()>n/2) return -1; if(second.size()>n/2) return -1;
스타트와 링크(15661번)
https://www.acmicpc.net/problem/15661
문제
위 문제에서 팀 N/2 조건이 없음.
풀이
import java.util.*;
public class Main {
static int n;
static int[][] s;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
s = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
s[i][j] = sc.nextInt();
}
}
ArrayList<Integer> first = new ArrayList<>();
ArrayList<Integer> second = new ArrayList<>();
System.out.println(go(0,first,second));
}
private static int go(int index, ArrayList<Integer> first, ArrayList<Integer> second) {
if(index==n) {
if(first.size()==0) return -1;
if(second.size()==0) return -1;
//인원수 체크
int t1 = 0;
int t2 = 0;
for (int i = 0; i < first.size(); i++) {
for (int j = 0; j < first.size(); j++) {
if(i==j) continue;
t1 += s[first.get(i)][first.get(j)];
}
}
for (int i = 0; i < second.size(); i++) {
for (int j = 0; j < second.size(); j++) {
if(i==j) continue;
t2 += s[second.get(i)][second.get(j)];
}
}
int diff = Math.abs(t1-t2);
return diff;
}
int ans = -1;
first.add(index);
int t1 = go(index+1,first,second);
if(ans==-1 || (t1!=-1&&ans>t1))
ans = t1;
first.remove(first.size()-1);
second.add(index);
int t2 = go(index+1,first,second);
if(ans==-1 || (t2!=-1&&ans>t2))
ans = t2;
second.remove(second.size()-1);
return ans;
}
}
부등호(2529번)
https://www.acmicpc.net/problem/2529
문제
- 부등호 기호 < 와 > 가 나열된 수열 A가 있다
- 기호의 앞 뒤에 한 자리 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다
- 이 때, 선택된 수는 모두 달라야 한다
- k개의 부등호 관계를 모두 만족시키는 (k+1)개 자리의 정수 중에서 최대값과 최소값을 구하는 문제
입력
첫 줄에 부등호 문자의 개수를 나타내는 정수 k. 그 다음 줄에는 k개의 부등호 기호가 하나의 공백을 두고 한 줄에 모두 제시. k의 범위는 2 ≤ k ≤ 9.
출력
제시된 부등호 관계를 만족하는 k+1 자리의 최대, 최소 정수를 첫째 줄과 둘째 줄에 각각 출력. 단 아래 예(1)과 같이 첫 자리가 0인 경우도 정수에 포함. 모든 입력에 답은 항상 존재하며 출력 정수는 하나의 문자열.
풀이
- 정수 넣을 수 있는 자리 k+1개, 즉 10개의 수를 10개의 자리에 넣음 10! = 3628800
- index, num(만든 수)
import java.util.*;
public class Main {
static int k;
static String[] a;
static boolean[] check = new boolean[10];
static ArrayList<String> ans = new ArrayList<String>();
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
k = sc.nextInt();
a = new String[k];
for(int i=0; i<k; i++) {
a[i] = sc.next();
}
go(0,"");
Collections.sort(ans);
int m = ans.size();
System.out.println(ans.get(m-1));
System.out.println(ans.get(0));
}
private static void go(int index, String num) {
if(index==k+1) {
ans.add(num);
return;
}
for(int i=0; i<10; i++) {
if(check[i]) continue;
if(index==0 || ok(num.charAt(index-1),(char)(i+'0'),a[index-1])) {
// i+'0' 는 int형을 char로 변환시키기 위함, 쓰지 않으면 i에 해당하는 아스키코드표 데이터가 나온다
check[i] = true;
go(index+1, num+i);
check[i] = false;
}
}
}
private static boolean ok(char x, char y, String a) {
// 백트래킹 조건 부분
for(int i=0; i<k; i++) {
if(a.equals("<")) {
if(x > y) return false;
}
else if(a.equals(">")) {
if(x < y) return false;
}
}
return true;
}
}
-> a[i]를 백준선생님처럼 char가 아니라 String으로 풀었는데 값이 나오지 않아 다른건 다 똑같은데 왜 안 되는거냐~~~! 했는데 String이라 ==가 아니라 equals를 써야했다.. ^^ㅠ맨날 까먹어
맞춰봐(1248번)
https://www.acmicpc.net/problem/1248
문제
- -10부터 10까지 N개의 정수로 이루어진 수열 A가 있다. (N≤10)
- S[ i ] [ j ] = A[ i ] + A[ i+1 ] + … + A[ j ]가 0보다 크면 +, 작으면 -, 같으면 0
- S가 주어졌을 때 가능한 A를 아무거나 찾는 문제
입력
첫째 줄에 수열의 크기 N(N≤10). 둘째 줄에는 N(N+1)/2 길이의 문자열. 처음 N개의 문자는 부호 배열의 첫 번째 줄에 해당하고, 다음 N-1개의 문자는 두 번째 줄에 해당한다. 마찬가지로 마지막 문자는 N번째 줄에 해당하는 문자다.
출력
첫째 줄에 수열의 원소 N개를 빈 칸을 사이에 두고 출력한다. 답이 여러 가지 일 경우에는 아무거나 출력하면 된다.
풀이
- 기준 : 수의 위치, 전체 경우의 수 21^10 = 16,679,880,978,201 따라서 브루투포스 백트래킹으로 풀어야 한다.
- s 배열에서 중요한 건 i, j가 같은 경우 = A[ i ]의 부호
- S[ i ][ j ] > 0 : 1~10
- S[ i ][ j ] = 0 : 0
- S[ i ][ j ] <> 0 : -10~-1
- 10^10 으로 경우의 수가 줄어듦 = 100억, 시간초과, 아이디어가 더 필요함
- S[ j ][ i ]의 부등호로 수 추리기
import java.util.*;
public class Main {
static int n;
static int[][] sign;
static int[] ans;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
ans = new int[n];
sign = new int[n][n];
String s = sc.next();
int cnt = 0;
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
char x = s.charAt(cnt);
if(x=='0')
sign[i][j]=0;
else if(x=='+')
sign[i][j]=1;
else if(x=='-')
sign[i][j]=-1;
cnt++;
}
}
go(0);
for(int i=0;i<n;i++) {
System.out.print(ans[i]+" ");
}
System.out.println();
}
private static boolean go(int index) {
if(index==n)
return true;
if(sign[index][index]==0) {
ans[index]=0;
return check(index) && go(index+1);
}
for(int i=1; i<=10; i++) {
ans[index] = sign[index][index]*i; //1~10 인지 -1~-10인지 범위 정함
if(check(index) && go(index+1))
return true;
}
return false;
}
private static boolean check(int index) {
//[i][index]들의 합으로 부등호를 비교해 수 범위 줄이기
int sum = 0;
for(int i=index; i>=0; i--) {
sum += ans[i];
if(sign[i][index] == 0) {
if(sum != 0)
return false;
} else if(sign[i][index] < 0) {
if(sum >= 0)
return false;
} else if(sign[i][index] > 0) {
if(sum <= 0)
return false;
}
}
return true;
}
}
댓글남기기