[완전탐색] 1244. 최대 상금 (Java)

[SWEA] 1244. 최대 상금

📌 풀이 과정

숫자의 자릿수를 교환하면서 최댓값을 찾는 문제다.
여기서 주의할 것은 반드시 횟수만큼 교환이 이루어져야 하고 동일한 위치의 교환이 중복되어도 된다.

DFS(조합 완탐) + 백트래킹

1. DFS로 완전 탐색
   교환할 수 있는 모든 자리 쌍에 대해 교환을 시도하고, 가능한 모든 경우를 재귀적으로 탐색한다.

2. 백트래킹
   교환한 후, 다음 탐색으로 넘어가기 전에 다시 원래 상태로 되돌려서 다른 교환을 시도할 수 있도록 한다.

✨ 제출 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Solution {

	static int swap, ans;
	static char[] money;
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int T = Integer.parseInt(br.readLine());
		for(int t = 1; t <= T; t++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			money = st.nextToken().toCharArray(); // 최대 자릿수
			swap = Integer.parseInt(st.nextToken()); // 교환 횟수
			ans = Integer.MIN_VALUE;
			
			if(money.length < swap) // swap 횟수가 자릿수보다 클 때 
				swap = money.length; // 자릿수만큼 옮겨도 전부 옮길 수 있다.
			
			dfs(0, 0);
			System.out.println("#" + t + " " + ans);
		}
		

	}
	
	static void dfs(int cnt, int start) {
		if(cnt == swap) {
			int sum = Integer.parseInt(String.valueOf(money));
			ans = Math.max(ans, sum);
			return;
		}
		
		for(int i = start; i < money.length - 1; i++) {
			for(int j = i + 1; j < money.length; j++) {
				swapNumber(i, j);
				dfs(cnt + 1, i); // 동일한 위치의 교환 중복 OK
				swapNumber(i, j);
			}
		}
	}
	
	static void swapNumber(int i, int j) {
		char tmp = money[i];
		money[i] = money[j];
		money[j] = tmp;
	}

}