[백준 1963] 소수 경로(Java)

1. 문제

www.acmicpc.net/problem/1963

1963번: 소수 경로

2. 풀이

• 에라토스테네스의 체를 활용하여 소수를 prime배열에 false로 저장해 놓았다.
• BFS를 활용하였고, 시작 숫자를 1000,100,10,1 자리수로 나눈 뒤 각 자리당 숫자를 넣어 계산하였다.

3. 코드

import java.io.*;
import java.util.*;

public class Main {

	static class Node {
		int num, cnt;

		public Node(int num, int cnt) {
			this.num = num;
			this.cnt = cnt;
		}

	}

	static boolean[] prime = new boolean[10000];
	static Queue<Node> que;
	static boolean[] visited;
	static int[] div = { 1000, 100, 10, 1 };
	static int result;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		//br = new BufferedReader(new StringReader(src));
		StringTokenizer st;

		// 소수 찾기
		prime[0] = true;
		prime[1] = true;
		for (int i = 2; i * i < 10000; i++) {
			for (int j = i * i; j < 10000; j += i) {
				prime[j] = true;
			}
		}

		int tc = Integer.parseInt(br.readLine());
		while (tc-- > 0) {
			result = Integer.MAX_VALUE;
			st = new StringTokenizer(br.readLine());
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
			visited = new boolean[10000];
			bfs(start, end);
			if(result == Integer.MAX_VALUE) {
				System.out.println("Impossible");
			}else System.out.println(result);
		}

	}

	static void bfs(int start, int end) {
		que = new LinkedList<>();
		que.offer(new Node(start, 0));
		visited[start] = true;
		while (!que.isEmpty()) {
			Node top = que.poll();
			if (top.num == end) {
				result = Math.min(result, top.cnt);
			}
			int[] number = new int[4];
			for (int i = 0; i < 4; i++) {
				number[i] = top.num / div[i];
				top.num %= div[i];
			}
			for (int i = 0; i <= 9; i++) {
				if (i != number[0]) {
					int next = i * 1000 + number[1] * 100 + number[2] * 10 + number[3] * 1;
					if (next >= 1000 && !prime[next] && !visited[next]) {
						visited[next] = true;
						que.offer(new Node(next, top.cnt + 1));
					}
				}
				if (i != number[1]) {
					int next = number[0] * 1000 + i * 100 + number[2] * 10 + number[3] * 1;
					if (next >= 1000 && !prime[next] && !visited[next]) {
						visited[next] = true;
						que.offer(new Node(next, top.cnt + 1));
					}
				}
				if (i != number[2]) {
					int next = number[0] * 1000 + number[1] * 100 + i * 10 + number[3] * 1;
					if (next >= 1000 && !prime[next] && !visited[next]) {
						visited[next] = true;
						que.offer(new Node(next, top.cnt + 1));
					}
				}
				if (i != number[3]) {
					int next = number[0] * 1000 + number[1] * 100 + number[2] * 10 + i * 1;
					if (next >= 1000 && !prime[next] && !visited[next]) {
						visited[next] = true;
						que.offer(new Node(next, top.cnt + 1));
					}
				}
			}
		}

	}

	static String src = "3\r\n" + "1033 8179\r\n" + "1373 8017\r\n" + "1033 1033";

}

반응형