https://www.acmicpc.net/problem/1039
1039번: 교환
첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다.
www.acmicpc.net
작년에 풀었을 때는 못풀었었는데 생각보다 간단한 bfs로 해결 가능한 문제였습니다.
이 문제는 swap(i번째 숫자, j번째 숫자)를 K번만큼 하였을 때 만들 수 있는 가장 큰 수를 출력하지만 K번의 연산을 할 수 없으면 -1을 출력해야합니다.
이 때, 바꾼수가 0으로 시작하면 안되기때문에 이에 대한 예외처리만 해주면 됩니다.
여기서 K번의 연산 후에 0으로 시작하는 수가 아닌 중간에도 0으로 시작하는 수가 나오면 안된다는 점을 주위하여야 합니다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 | import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; public class Main { static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static StringTokenizer st; static boolean visit[][] = new boolean[1000001][11]; static int N, K, ans = -1; static void bfs() { Queue<int[]> q = new LinkedList<>(); q.add(new int[] { N, 0 }); visit[N][0] = true; while (!q.isEmpty()) { int xx = q.peek()[0]; char x[] = Integer.toString(xx).toCharArray(); int cnt = q.peek()[1]; q.remove(); if (cnt == K) { ans = Math.max(ans, xx); continue; } char newx[]; for (int i = 0; i < x.length; i++) { for (int j = i + 1; j < x.length; j++) { if (i == 0 && x[j] == '0') continue; newx = x.clone(); char temp = newx[i]; newx[i] = newx[j]; newx[j] = temp; int y = Integer.parseInt(String.valueOf(newx)); if (!visit[y][cnt + 1]) { q.add(new int[] { y, cnt + 1 }); visit[y][cnt + 1] = true; } } } } } static void input() throws Exception { st = new StringTokenizer(br.readLine()); N = Integer.parseInt(st.nextToken()); K = Integer.parseInt(st.nextToken()); } public static void main(String[] args) throws Exception { input(); bfs(); System.out.println(ans); } } | cs |
'algorithm > bfs' 카테고리의 다른 글
| boj 17142 연구소 3 (0) | 2021.01.22 |
|---|---|
| boj 2636 치즈 (0) | 2021.01.22 |
| boj 3055 탈출 (0) | 2021.01.22 |
| boj 2234 성곽 (0) | 2021.01.22 |
| boj 17472 다리 만들기 2 (0) | 2021.01.22 |