[swea/java] 1244. 최대 상금

문제

퀴즈 대회에 참가해서 우승을 하게 되면 보너스 상금을 획득할 수 있는 기회를 부여받는다. 우승자는 주어진 숫자판들 중에 두 개를 선택에서 정해진 횟수만큼 서로의 자리를 위치를 교환할 수 있다.
예를 들어, 다음 그림과 3, 2, 8, 8, 8 의 5개의 숫자판들이 주어지고 교환 횟수는 2회라고 하자. 처음에는 첫번째 숫자판의 3과 네 번째 숫자판의 8을 교환해서 8, 2, 8, 3, 8이 되었다. 다음으로, 두 번째 숫자판 2와 마지막에 있는 8을 교환해서 8, 8, 8, 3, 2이 되었다.

 

정해진 횟수만큼 교환이 끝나면 숫자판의 위치에 부여된 가중치에 의해 상금이 계산된다. 숫자판의 오른쪽 끝에서부터 1원이고 왼쪽으로 한자리씩 갈수록 10의 배수만큼 커진다.
위의 예에서와 같이 최종적으로 숫자판들이 8,8,8,3,2의 순서가 되면 88832원의 보너스 상금을 획득한다.

여기서 주의할 것은 반드시 횟수만큼 교환이 이루어져야 하고 동일한 위치의 교환이 중복되어도 된다. 다음과 같은 경우 1회의 교환 횟수가 주어졌을 때 반드시 1회 교환을 수행하므로 결과값은 49가 된다.

 

우선 풀이를 말하기 앞서 dfs와 백트래킹에 관한 기초 지식이 있으면 이해하기 쉽습니다. 

 

간단하게 DFS는 깊이 우선 탐색으로, 다른 가지로 넘어가기 전에 한 경로를 끝까지 탐색하는 방법입니다.
백트래킹은 DFS로 경로를 탐색하면서, 불필요하거나 이미 방문한 상태를 만나면 되돌아와 다른 경로를 탐색하는 최적화 기법입니다.

 

 

이 두가지를 활용해서 이번 문제를 풀어볼 건데요, 

 

1. 입력값을 char 배열로 만든 뒤

2. 배열을 돌며 값의 위치들을 바꾸고 visited에 저장합니다. 

2-1. 교환 횟수가 0이면 현재 배열을 숫자로 변환한 뒤 max와 비교합니다

       max가 더 작다면 현재 값을 max로 바꿉니다.

 

 

import java.util.*;
public class Solution {
	
	static int max;
	static HashSet<String> visited;
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt(); //테스트 케이스 개수
		
		for(int tc = 1 ; tc<=T; tc++) {
			String num = sc.next();
			int k = sc.nextInt();
			
			char[] arr = num.toCharArray();
			
			max = 0;
			
			visited = new HashSet<>();
			
			dfs(arr, k);
			
			System.out.println("#" + tc + " " + max);
		}		
	}
	
	static void dfs(char[] arr, int k) {
		if(k==0) {
			//교환 종료 시 현재 값과 max 값 크기 비교 후 값 리턴
			int val = Integer.parseInt(new String(arr)); 
			
			if(val > max)
				max = val;
			return;
		}
		
		String state = new String(arr) + "/" + k;
		
		//이미 방문한 적 있으면 종료
		if(visited.contains(state))
			return;
		visited.add(state);

		//배열을 돌며 모든 자리 교환
		for(int i = 0; i < arr.length  - 1 ; i++) {
			for(int j = i+1 ; j < arr.length; j++) {
				swap(arr, i , j);
				dfs(arr, k - 1);
				swap(arr, i ,j); //원상복구(백트래킹)
			}
		}
	}
	//위치 바꾸기
	static void swap(char[] arr, int i, int j) {
		char temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}

}

 

너무 헷갈렸습니다..ㅠ