백준 1963번 소수 경로 (C++)

어제부터 그래프 탐색 문제를 건드리는 중이다.
오늘은 그 중 하나인 소수 경로라는 문제에 대해 알아보자.

문제링크

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

설명

간단하게 처음 들어오는 수가 나중에 들어오는 수로 바뀌는데 몇 번의 과정을 거치는가를 구하는 문제이다.
맨 처음 5분 동안은 이걸 어떻게 하지...?라는 생각이 들었는데 그냥 내 생각대로 풀었다. 이렇게 풀 수 있을려나...?라고 생각하면서 망설이는 시간에 코드를 직접 쳐보면서 이게 되는지 안 되는지 빠르게 판단하는게 더 중요한 거 같다. 이 문제는 이렇게 풀 수 있는 문제였다.
주의할 점은 테스트케이스가 여러 개이기 때문에 이전 케이스에서 사용한 큐와 visited 배열을 항상 초기화해주어야 한다는 것이다.
그리고 불가능한 경우는 없다고 하더라... 그래도 큐를 다 돌 때까지 결과값이 반환되지 않았을 때 Impossible을 출력하게끔 하자.

코드

#include <iostream>
#include <vector>
#include <queue>

using namespace std;
vector<int> primenum(10000), visited(10000);
queue<pair<int, int>> changepw;

void makeprimenum()
{
	primenum[1] = 1;
	for (int i = 2; i < 10000; i++)
	{
		if (!primenum[i])
		{
			for (int j = i * 2; j < 10000; j += i)
				primenum[j] = 1;
		}
	}
}

int solve(int a, int b)
{
	changepw.push({ a,0 });
	visited[a] = 1;

	while (!changepw.empty())
	{
		int num = changepw.front().first;
		int cnt = changepw.front().second;
		changepw.pop();

		if (num == b)
			return cnt;

		for (int i = 1000; i <= 9000; i += 1000)
		{
			int nextnum = i + num % 1000;
			if (!primenum[nextnum] && !visited[nextnum])
			{
				visited[nextnum] = 1;
				changepw.push({ nextnum,cnt + 1 });
			}
		}

		for (int i = 0; i <= 900; i += 100)
		{
			int nextnum = num / 1000 * 1000 + i + num % 100;
			if (!primenum[nextnum] && !visited[nextnum])
			{
				visited[nextnum] = 1;
				changepw.push({ nextnum,cnt + 1 });
			}
		}

		for (int i = 0; i <= 90; i += 10)
		{
			int nextnum = num / 100 * 100 + i + num % 10;
			if (!primenum[nextnum] && !visited[nextnum])
			{
				visited[nextnum] = 1;
				changepw.push({ nextnum,cnt + 1 });
			}
		}

		for (int i = 0; i <= 9; i++)
		{
			int nextnum = num / 10 * 10 + i;
			if (!primenum[nextnum] && !visited[nextnum])
			{
				visited[nextnum] = 1;
				changepw.push({ nextnum,cnt + 1 });
			}
		}
	}

	return -1;
}

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int testcase, a, b, result;
	makeprimenum();
	cin >> testcase;
	while (testcase--)
	{
		cin >> a >> b;
		result = solve(a, b);
		result >= 0 ? cout << result << '\n' : cout << "Impossible\n";
		fill(visited.begin(), visited.end(), 0);
		while (!changepw.empty())
			changepw.pop();
	}
	return 0;
}