[백준] 1963번 - 소수 경로 / C++

문제

소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데:

• “이제 슬슬 비번 바꿀 때도 됐잖아”
• “응 지금은 1033으로 해놨는데... 다음 소수를 무엇으로 할지 고민 중이야"
• “그럼 8179로 해”
• “흠... 생각 좀 해볼게. 이 게임은 좀 이상해서 비밀번호를 한 번에 한 자리밖에 못 바꾼단 말이야. 예를 들어 내가 첫자리만 바꾸면 8033이 되니까 소수가 아니잖아. 여러 단계를 거쳐야 만들 수 있을 것 같은데... 예를 들면... 1033 1733 3733 3739 3779 8779 8179처럼 말이야.”
• “흠... 역시 소수에 미쳤군. 그럼 아예 프로그램을 짜지 그래. 네 자리 소수 두 개를 입력받아서 바꾸는데 몇 단계나 필요한지 계산하게 말이야.”
• “귀찮아”

그렇다. 그래서 여러분이 이 문제를 풀게 되었다. 입력은 항상 네 자리 소수만(1000 이상) 주어진다고 가정하자. 주어진 두 소수 A에서 B로 바꾸는 과정에서도 항상 네 자리 소수임을 유지해야 하고, ‘네 자릿수’라 하였기 때문에 0039와 같은 1000 미만의 비밀번호는 허용되지 않는다.

 

입력

첫 줄에 test case의 수 T가 주어진다. 다음 T 줄에 걸쳐 각 줄에 1쌍씩 네 자리 소수가 주어진다.

 

출력

각 test case에 대해 두 소수 사이의 변환에 필요한 최소 횟수를 출력한다. 불가능한 경우 Impossible을 출력한다.

 

코드

#include <iostream>
#include <queue>
#include <cstring>
#include <cmath>

using namespace std;

int prime[10000];	// 소수인지 아닌지 (-1: 확인 안 됨, 0: 소수 아님, 1: 소수 맞음)
int visit[10000];	// 확인 여부 및 최소 횟수 (-1: 확인 안 됨, 0 이상: 최소 횟수)
string s, e;		// s: 기존 비밀번호, e: 바꿀 비밀번호

bool is_prime(int n)
{
	int i;

	for (i = 2; i <= sqrt(n); i++)
	{
		if (n % i == 0)
			return false;
	}
	return true;
}

int bfs()
{
	queue<string> q;
	string curr, next;
	char d[] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};
	int i, j;

	// 초기화
	memset(visit, -1, sizeof(visit));
	// 시작 비밀번호에 대해 최소 횟수를 저장하고 큐에 삽입
	prime[stoi(s)] = 1;
	visit[stoi(s)] = 0;
	q.push(s);
	while (!q.empty())
	{
		curr = q.front();
		q.pop();
		// 바꿀 비밀번호인 경우 최소 횟수 리턴
		if (curr.compare(e) == 0)
			return visit[stoi(curr)];
		// 긱 자리에 대해
		for (i = 0; i < 4; i++)
		{
			// 0부터 9까지의 숫자로 변경해 봄
			for (j = 0; j < 10; j++)
			{
				// 첫 번째 자리를 0으로 바꾸는 것은 불가능
				if (i == 0 && j == 0)
					continue;
				next = curr;
				next[i] = d[j];
				// 이미 확인한 적이 있으면 패스
				if (visit[stoi(next)] != -1)
					continue;
				// 소수 여부가 확인되지 않았으면 확인
				if (prime[stoi(next)] == -1)
					prime[stoi(next)] = is_prime(stoi(next));
				// 소수가 아니면 패스
				if (!prime[stoi(next)])
					continue;
				// 최소 횟수를 저장하고 큐에 삽입
				visit[stoi(next)] = visit[stoi(curr)] + 1;
				q.push(next);
			}
		}
	}
	// 변경할 수 없는 경우
	return -1;
}

int main()
{
	int t, T;
	int res;

	cin >> T;
	memset(prime, -1, sizeof(prime));
	for (t = 0; t < T; t++)
	{
		s.clear();
		e.clear();
		cin >> s >> e;
		res = bfs();
		if (res < 0)
			cout << "Impossible" << endl;
		else
			cout << res << endl;
	}
	return 0;
}

 

링크

1963번: 소수 경로

inbdni/Baekjoon