1244. [S/W 문제해결 응용] 2일차 - 최대 상금

문제 출처 : https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15Khn6AN0CFAYD&categoryId=AV15Khn6AN0CFAYD&categoryType=CODE

DFS 방식으로 구현했고, check 배열을 사용하여

같은 횟수이면서 같은 숫자를 탐색했는지 체크했습니다.

따라서 불필요한 탐색을 수행하지 않게되죠.

문제를 보니 DFS or BFS를 사용해야 할 것 같아,

백준사이트에서 DFS or BFS 문제를 조금 풀고왔는데 도움되네요.

package sw; import java.util.Scanner; public class Q1244 { static int result, maxCount; static boolean[][] check; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int max = sc.nextInt(); for ( int i = 1; i <= max; i++ ) { String number = sc.next(); maxCount = sc.nextInt(); check = new boolean[maxCount+1][1000000]; // 같은 횟수이면서 같은 숫자를 탐색했는지 체크 result = 0; changeNumber(number.toCharArray(), 0); System.out.println("#" + i + " " + result); } } public static void changeNumber(char[] numberChar, int nowCount) { if ( maxCount == nowCount ) { //횟수만큼 바꿨으면 결과 입력하고 종료 result = result > getInteger(numberChar) ? result : getInteger(numberChar); return; } int max = numberChar.length; for (int i = 0; i < max - 1; i++ ) { for ( int j = i+1; j < max; j++ ) { char[] tempNumber = swap(numberChar, i, j); //해당 자리 바꾼 char[] 받아오기 if ( !check[nowCount+1][getInteger(tempNumber)] ) { //같은 횟수이면서 같은 숫자를 탐색하지 않았으면 탐색 check[nowCount+1][getInteger(tempNumber)] = true; changeNumber(tempNumber, nowCount+1); } } } } public static int getInteger(char[] numberChar) { return Integer.valueOf(String.valueOf(numberChar)); } public static char[] swap(char[] numberChar, int point1, int point2) { //해당 자리의 숫자 바꾸기 char[] tempNumber = numberChar.clone(); char num = tempNumber[point1]; tempNumber[point1] = tempNumber[point2]; tempNumber[point2] = num; return tempNumber; } }