소수 경로

문제

언어

  • JavaScript

순서도

  1. 에라토스테네스의 체를 이용해서 4 자리의 소수 모두 찾기
  2. 각 테스트케이스마다 BFS 탐색을 하면서 비밀번호 변환에 필요한 최소 회수 구하기

문제 풀이 step 1

  • 소수를 유난히도 좋아하는 창영이는 게임 비밀번호를 4자리 ‘소수’로 정해놓았습니다.
  • 비밀번호를 바꾸려고 하는데 게임이 좀 이상해서 비밀번호를 한 번에 한 자리 밖에 못바꿉니다.
  • 그래서 특정 4자리의 ‘소수’로 바꾸기 위해서 몇 단계가 필요할지 궁금합니다.
  • 입력은 항상 네 자리 소수만(1000 이상) 주어진다고 가정합니다.
  • 주어진 두 소수 A 에서 B 로 바꾸는 과정에서도 항상 네 자리 소수임을 유지해야 합니다.
  • 그리고 ‘네 자리 수’라 하였기 때문에 0039 와 같은 1000 미만의 비밀번호는 허용되지 않습니다.

문제 풀이 step 2

  • 위의 설명을 토대로 각 테스트 케이스에 대해서 두 소수 사이의 변환에 필요한 최소 회수를 구하는 문제입니다.
  • 본 문제는 수학, BFS (+ 브루트포스) 개념을 필요로 하는 문제입니다.
    • 소수 판별을 위해서 수학의 에라토스테네스의 체에 대한 개념이 들어갑니다.
    • 그리고 가능한 모든 소수를 검사해보기 위해서 BFS 탐색에 대한 개념이 들어갑니다.
  • 우선, 에라토스테네스의 체를 이용해서 4자리의 모든 소수를 구합니다.
  • 그리고 BFS 탐색을 하면서 현재 탐색하려는 숫자가 소수인지, 이미 탐색을 했는지 검사해가며 바꾸려고 하는 비밀번호에 도달했는지 검사합니다.
    • BFS 탐색은 단계별로 진행을 하기 위해서 두 개의 큐를 사용합니다.
    • 다음에 탐색할 경로를 다음 큐에 넣어주고, 현재 큐가 비면 현재 큐에 다음 큐에 들어있는 경로를 넣어주는 방식으로 단계별로 탐색을 진행합니다.
    • 비밀번호를 바꿀 때 한 번에 한 자리 밖에 못바꾸기 때문에 다음에 탐색할 경로는 현재의 비밀 번호에서 한 자리씩 값을 바꾼 값이 되겠습니다.
  • 최종적으로 바꾸려고 하는 비밀번호에 도달하기 위한 단계의 수를 출력하면 정답입니다.
  • 추가 설명은 주석으로 작성하겠습니다.

후기

  • 최근에 풀었던 2251 번 물통 문제 덕분에 BFS 탐색 기법을 생각해낼 수 있었습니다.
    • 이와 같은 방식의 문제들을 풀면서, BFS 탐색 기법이 브루트포스 기법과 닮은 것 같다는 생각을 했습니다.
    • 결국은 많이 푸는 것이 정답인 것 같습니다.
  • 수학 카테고리에서 찾은 문제이지만, BFS 탐색이 더 핵심이라고 생각해서 BFS 카테고리에 넣었습니다.

소스 코드

const input = require("fs")
	.readFileSync("/dev/stdin")
	.toString()
	.trim()
	.split("\n");

class Queue {
	constructor() {
		this.bucket = [];
		this.front = -1;
		this.rear = -1;
	}

	enqueue(data) {
		this.bucket[++this.rear] = data;
	}

	dequeue() {
		return this.bucket[++this.front];
	}

	isEmpty() {
		return this.front === this.rear;
	}
}

const BFS = (a, b, isPrime, visited) => {
	let queue = new Queue();
	let nextQueue = new Queue();

	let depth = 1;
	queue.enqueue(a);
	visited[Number(a.join(""))] = true;

	while (!queue.isEmpty()) {
		const from = queue.dequeue();

		// 각 자리마다 0 ~ 9 를 넣는 방식을 통해서 다음 탐색할 경로 찾기
		for (let i = 0; i < 4; i++) {
			for (let j = 0; j < 10; j++) {
				if (i === 0 && j === 0) continue;

				const to = [...from];
				to[i] = j;
				const numTo = Number(to.join(""));

				// 소수가 아니거나 이미 방문했다면,
				if (!isPrime[numTo]) continue;
				if (visited[numTo]) continue;

				// 바꾸려고 하는 비밀번호에 도달했다면,
				if (numTo === b) {
					return depth;
				}

				// 방문 처리 후 다음 큐에 넣어주기
				visited[numTo] = true;
				nextQueue.enqueue(to);
			}
		}

		// 현재 큐가 비었다면, 다음 큐에서 경로를 가져오고, 한 단계 증가
		if (queue.isEmpty()) {
			queue = nextQueue;
			nextQueue = new Queue();
			depth += 1;
		}
	}

	return "Impossible";
};

const solution = (input) => {
	// 에라토스테네스의 체를 이용해서 소수 판별을 위한 배열 생성
	const isPrime = Array(10000).fill(true);
	isPrime[0] = isPrime[1] = false;
	for (let i = 2; i < 10000; i++) {
		if (isPrime[i] === false) continue;

		for (let j = i + i; j < 10000; j += i) {
			isPrime[j] = false;
		}
	}

	const t = Number(input[0]);

	let res = "";
	for (let i = 1; i < t + 1; i++) {
		let [a, b] = input[i].split(" ");
		// 변환할 필요가 없다면 0 출력
		if (a === b) {
			res += "0\n";
			continue;
		}

		[a, b] = [a.split("").map(Number), Number(b)]; // [1, 0, 3, 3], 8179
		const visited = Array(10000).fill(false);

		// BFS 탐색을 통해서 변환하는데 필요한 단계의 수 구하기
		res += `${BFS(a, b, isPrime, visited)}\n`;
	}

	return res;
};

console.log(solution(input));