[백준]JAVA - 1039번: 교환

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

1039번: 교환

풀이

처음엔 완전 탐색으로 접근했다가 메모리 초과가 발생했다.

 

2중 for문을 이용해서 모든 경우의 수를 변경해준다.

이 과정에서 visited[number][cnt] 2차원 배열로 자리를 바꾼 후에 생기는 중복된 수를 제거했다. 

 

중복된 수를 제거할 때는 변경 횟수도 중요하다.

변경된 숫자가 같더라도 1번 변경했을 때 나온 A와 2번 변경했을 때 나오는 B는 전혀 다르다.

그렇기 때문에 변경 횟수도 방문 여부를 체크해줄 때 꼭 필요하다.

for (int i=0; i<len-1; i++) {
    for (int j=i+1; j<len; j++) {
        int tmp = doChange(i, j, n.num);
					
        if (tmp != -1 && !visited[tmp][n.cnt+1]) {
            q.add(new Number(tmp, n.cnt+1));
            visited[tmp][n.cnt+1] = true;
        }
    }
}
 
public static int doChange(int i, int j, int num) {
    char[] arrChar = String.valueOf(num).toCharArray();
		
    // 첫 번째 자리에 '0'이 올 수 없음
    if (i == 0 && arrChar[j] == '0') {
        return -1;
    }
		
    char tmp;
    tmp = arrChar[i];
    arrChar[i] = arrChar[j];
    arrChar[j] = tmp;
		
    return Integer.parseInt(new String(arrChar));
}

숫자를 교환하는 과정에서 int형 → char형 배열 → String형으로 변환하는 걸 잘 모르면 위 문제가 어려워질 수 있다. 다른 곳에서도 사용될 수 있으니까 기억해두는 게 좋다.

 

 

<최종코드>

import java.io.*;
import java.util.*;
 
public class Main {
    static int N, K;
    static int ans = -1;
	
    public static class Number {
        int num;
        int cnt;
		
        public Number (int num, int cnt) {
            this.num = num;
            this.cnt = cnt;
        }
    }
	
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
		
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
		
        bfs();
        System.out.println(ans);
    }
	
    public static void bfs() {
        Queue<Number> q = new LinkedList<>();
        boolean[][] visited = new boolean[1000001][K+1]; // 최대 숫자가 1,000,000
		
        q.add(new Number(N, 0));
        visited[N][0] = true;
		
        while (!q.isEmpty()) {
            Number n = q.poll();
			
            if (n.cnt == K) {
                ans = Math.max(ans, n.num);
                continue;
            }
			
            int len = String.valueOf(N).length();
			
            for (int i=0; i<len-1; i++) {
                for (int j=i+1; j<len; j++) {
                    int tmp = doChange(i, j, n.num);
					
                    if (tmp != -1 && !visited[tmp][n.cnt+1]) {
                        q.add(new Number(tmp, n.cnt+1));
                        visited[tmp][n.cnt+1] = true;
                    }
                }
            }
        }
    }
	
    public static int doChange(int i, int j, int num) {
        char[] arrChar = String.valueOf(num).toCharArray();
		
        // 첫 번째 자리에 '0'이 올 수 없음
        if (i == 0 && arrChar[j] == '0') {
            return -1;
        }
		
        char tmp;
        tmp = arrChar[i];
        arrChar[i] = arrChar[j];
        arrChar[j] = tmp;
		
        return Integer.parseInt(new String(arrChar));
    }
}