백준 1963번: 소수 경로

[문제 링크]

1963번: 소수 경로

---

너비 우선 탐색으로 풀 수 있는 문제였다.

 

먼저 크기가 10000인 prime 배열을 선언하고, 에라토스테네스의 체 알고리즘을 통해 소수가 아닌 숫자들을 true로 바꿔주었다.

 

그다음 문제 조건에 따라 너비 우선 탐색을 통해 A의 숫자를 한개씩 바꾸면서 숫자 B와 일치할 때까지 바꾼 최소 횟수를 구해주면 된다.

---

#include <iostream>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

bool prime[10000];
bool visited[10000];

void getPrime() {
	prime[1] = true;

	for (int i = 2; i < 10000 / 2; i++) {
		if (prime[i]) continue;

		for (int j = i * 2; j < 10000; j += i)
			if (!prime[j]) 
				prime[j] = true;
	}
}

int bfs(int a, int b) {
	queue<pair<int, int>> q;
	q.push({ a, 0 });
	visited[a] = true;

	while (!q.empty()) {
		int here = q.front().first;
		int move = q.front().second;
		q.pop();

		if (here == b) return move;

		for (int i = 1; i <= 4; i++) {
			int there;
			switch (i) {
			case 1: // 1000의 자리
				for (int j = 1; j <= 9; j++) {
					there = (j * 1000) + (here % 1000);
					if (!visited[there] && !prime[there]) {
						visited[there] = true;
						q.push({ there, move + 1 });
					}
				}
				break;

			case 2: // 100의 자리
				for (int j = 0; j <= 9; j++) {
					there = (here / 1000 * 1000) + (j * 100) + (here % 100);
					if (!visited[there] && !prime[there]) {
						visited[there] = true;
						q.push({ there, move + 1 });
					}
				}
				break;

			case 3: // 10의 자리
				for (int j = 0; j <= 9; j++) {
					there = (here / 100 * 100) + (j * 10) + (here % 10);
					if (!visited[there] && !prime[there]) {
						visited[there] = true;
						q.push({ there, move + 1 });
					}
				}
				break;

			case 4: // 1의 자리
				for (int j = 0; j <= 9; j++) {
					there = (here / 10 * 10) + j;
					if (!visited[there] && !prime[there]) {
						visited[there] = true;
						q.push({ there, move + 1 });
					}
				}
			}
		}
	}

	return -1;
}

int main(void) {
	int tc;
	cin >> tc;

	getPrime();

	while (tc--) {
		memset(visited, false, sizeof(visited));
		int a, b;
		cin >> a >> b;

		int result = bfs(a, b);

		if (result == -1)
			cout << "Impossible" << endl;
		else
			cout << result << endl;
	}
}

알고리즘 200일 프로젝트 - 168 day