[백준_1039번] 교환

https://www.acmicpc.net/problem/1039

1039번: 교환

[문제]

0으로 시작하지 않는 정수 N이 주어진다. 이때, M을 정수 N의 자릿수라고 했을 때, 다음과 같은 연산을 K번 수행한다.

"1 ≤ i < j ≤ M인 i와 j를 고른다. 그 다음, i번 위치의 숫자와 j번 위치의 숫자를 바꾼다. 이때, 바꾼 수가 0으로 시작하면 안 된다."

 위의 연산을 K번 했을 때, 나올 수 있는 수의 최댓값을 구하는 프로그램을 작성하시오.

 

[입력 조건]

첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다.

 

[코드]

import java.util.*;

class Point_1039 {
	int num, count;
	
	public Point_1039(int num, int count) {
		this.num=num;
		this.count=count;
	}
}

public class BaekJoon_1039 {
	static int n,k,max=-1;
	static boolean[][] visited;
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		
		n=sc.nextInt();
		k=sc.nextInt();
		
		visited=new boolean[1000001][k+1];
		
		bfs();
		System.out.println(max);
	}

	static void bfs() {
		Queue<Point_1039> q=new LinkedList<>();
		q.offer(new Point_1039(n,0));
		
		while(!q.isEmpty()) {
			Point_1039 p=q.poll();
			
			// k번 이동해서 만들어진 수라면 max 갱신
			if(p.count==k) {
				max=Math.max(max, p.num);
				continue;
			}
			
			// 현재 정수의 각 자리수를 swap 할 수 있는 모든 경우의 수 탐색 
			int length=String.valueOf(p.num).length();
			for(int i=0;i<length;i++) {
				for(int j=i+1;j<length;j++) {
					int result=swap(p.num,i,j);
					
					/*
					 * 두 자릿수를 swap 할 수 있고 p.count+1번째 이동 횟수에서 
					 * 만들어진 적 없는 수라면 큐에 삽입
					 */
					if(result!=-1&&!visited[result][p.count+1]) {
						q.offer(new Point_1039(result,p.count+1));
						visited[result][p.count+1]=true;
					}
				}
			}
		}
	}
	
	// i번째 수와 j번째 수를 바꾸는 함수
	static int swap(int num, int i, int j) {
		// 정수 num을 각 자리수를 배열에 따로 저장
		char[] ch=String.valueOf(num).toCharArray();
		
		// swap한 결과의 첫 번쨰 자리수가 0이라면 불가능한 경우
		if(i==0&&ch[j]=='0')
			return -1;
		
		// swap
		char temp=ch[i];
		ch[i]=ch[j];
		ch[j]=temp;
		
		// 배열을 다시 정수로 변환하여 return
		return Integer.parseInt(new String(ch));
	}
}

 

[고찰]

 이번 문제는 어떤 알고리즘을 사용해야 하는지 캐치하는 부분이 가장 어려웠다. 고민 결과 BFS 알고리즘을 사용하여 해결할 수 있었다. 정수 n의 각 자리수를 swap 할 수 있는 모든 경우의 수를 체크하면서 이동 횟수가 k를 만족했을 때 max 값을 갱신해주면 되었다. 이때 해당 숫자가 이미 만들어진 숫자인지도 확인해야 하기 때문에 2차원 배열을 사용하는 방식으로 해결하였다.