백준 1039번
https://www.acmicpc.net/problem/1039
문제
생각하기
- 좋은 문제이다.
- 백트래킹과 DP를 함께 사용해야 해결할 수 있는 문제이다.
- 메모이제이션을 사용해야 됨
- 방문했던 곳의 최대값을 알 경우 가지치기를 할 수 있음
- 쉬워보이지만 굉장히 까다로운 문제
동작
memo = new int[K + 1][1000001];
방문 여부를 체크하고, 재귀 깊이를 행으로 해서 인덱스로 값을 체크할 메모이제이션 배열이다.
if (depth == K) {
return num;
}
재귀의 깊이가 K와 같아 졌을 때 return 한다. (백트래킹 개념)
즉, 교환 연산의 횟수와 재귀의 깊이가 같을 때, (K번 교환을 마쳤다는 의미)
int memoValue = memo[depth][num];
if (memoValue != 0) {
return memoValue;
}
여기서 DP의 메모이제이션 개념이 적용된다
재귀 깊이에서 같은 값이 들어왔을 경우 -> memo[depth][num] 이 0이 아닐경우 -> 해당 값을 return하고 종료 하도록 해서 가지치기를 수행한다.
for (int i = 0; i < M - 1; i++) {
for(int j=i+1; j<M; j++) {
if(i == 0 && strN.charAt(j) == '0') { // 바꾸려고 할 때, 첫번째 자리 0이 들어오려고 하면, 그냥 넘어감.
continue;
}
String swapStr = swap(strN, i, j);
int temp = DFS(swapStr, depth + 1);
memoValue = Math.max(memoValue, temp);
}
}
바깥의 i와 안쪽 j를 스왑하는 방식으로 두 숫자의 위치를 바꾼다.
숫자의 위치를 바꾼 후 바뀐 숫자로 DFS를 또 실행하고 재귀의 깊이인 depth를 +1 해준다.
이후 DFS에서 return 받은 값을 최댓값과 비교를 하며 갱신하는 구조이다.
핵심은 K번의 연산을 수행 후 return 되거나, 이미 있는 값은 가지치기로 돌려받는 값
이 2가지를 만들며 최댓값을 찾는다.
DFS
BFS
코드
Java
DFS
import java.util.*;
import java.io.*;
public class Main {
static int memo[][];
static int K;
static int M;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
String N = st.nextToken();
K = Integer.parseInt(st.nextToken());
M = N.length();
memo = new int[K + 1][1000001];
System.out.println(DFS(N, 0));
} // End of main
private static int DFS(String strN, int depth) {
int num = Integer.parseInt(strN);
if (depth == K) {
return num;
}
int memoValue = memo[depth][num];
if (memoValue != 0) {
return memoValue;
}
memoValue = -1; // 불가능할 경우 -1을 가져오기 위해 -1로 초기화
for (int i = 0; i < M - 1; i++) {
for(int j=i+1; j<M; j++) {
if(i == 0 && strN.charAt(j) == '0') { // 바꾸려고 할 때, 첫번째 자리 0이 들어오려고 하면, 그냥 넘어감.
continue;
}
String swapStr = swap(strN, i, j);
int temp = DFS(swapStr, depth + 1);
memoValue = Math.max(memoValue, temp);
}
}
memo[depth][num] = memoValue;
return memo[depth][num];
} // End of DFS
private static String swap(String str, int i, int j) {
char chArr[] = str.toCharArray();
char temp = chArr[i];
chArr[i] = chArr[j];
chArr[j] = temp;
return String.valueOf(chArr);
} // End of swap
} // End of Main class
BFS
import java.io.*;
import java.util.LinkedList;
import java.util.StringTokenizer;
public class Main {
// input
private static BufferedReader br;
// variables
private static int N, K, M;
private static String str;
private static boolean[][] memo;
private static class Num {
int num;
int count;
private Num(int num, int count) {
this.num = num;
this.count = count;
}
} // End of Num class
public static void main(String[] args) throws IOException {
br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
input();
bw.write(solve());
bw.close();
} // End of main()
private static String solve() {
StringBuilder sb = new StringBuilder();
sb.append(BFS());
return sb.toString();
} // End of solve()
private static int BFS() {
LinkedList<Num> que = new LinkedList<>();
que.offer(new Num(N, 0));
memo[N][0] = true;
int ans = -1;
while (!que.isEmpty()) {
Num current = que.poll();
if (current.count == K) {
ans = Math.max(ans, current.num);
continue;
}
String s = Integer.toString(current.num);
for (int i = 0; i < M - 1; i++) {
for (int j = i + 1; j < M; j++) {
if (i == 0 && s.charAt(j) == '0') continue;
int swapNum = swap(i, j, Integer.parseInt(s));
if (memo[swapNum][current.count + 1]) continue;
memo[swapNum][current.count + 1] = true;
que.offer(new Num(swapNum, current.count + 1));
}
}
}
return ans;
} // End of BFS()
private static int swap(int i, int j, int num) {
char[] ch = Integer.toString(num).toCharArray();
char temp = ch[i];
ch[i] = ch[j];
ch[j] = temp;
return Integer.parseInt(String.valueOf(ch));
} // End of swap()
private static void input() throws IOException {
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
str = Integer.toString(N);
M = str.length();
memo = new boolean[1_000_001][K + 1];
} // End of input()
} // End of Main class
