[백준 1963] 소수 경로

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

1963번: 소수 경로

#include <cstdio>
#include <cmath>
#include <iostream>
#include <queue>
int T;		// 테케 수
int s, e;	// s : 현재 비밀번호	e : 바꿀 비밀번호

int visited[10000];	//최대 9999
struct _st
{
	int current;
	int cnt;
};

std::queue<_st> Q;

void init(void)
{
	Q = {};	// 큐 초기화
	for (int i = 1000; i <= 9999; i++) {
		visited[i] = 0;	// 방문배열 초기화 
	}
}


int is_prime(int num)	// 소수 판별
{
	for (int i = 2; i <= sqrt(num); i++) {
		if (num % i == 0) return 0;
	}
	return 1;
}


int password(void)
{
	if (s == e) return 0;	// 현재 비밀번호와 바꿀 비밀번호가 같은 경우 
	
	Q.push({ s, 0 });
	visited[s] = 1;

	while (!Q.empty()) {
		_st data = Q.front();
		Q.pop();

		for (int pow = 1; pow <= 1000; pow *= 10) {
			int del_num = data.current / pow % 10;	// 자리값 추출 
			int make_zero = data.current - (del_num * pow);	// 해당 자리값을 0으로 만듦

			// 만약 pow가 천의 자리이면 1~9까지 올 수 있음
        		// pow가 일, 십, 백의 자리이면 0~9까지 올 수 있음
			for (int d = (pow == 1000) ? 1 : 0; d <= 9; d++) {
				int npassword = make_zero + (d * pow);
				int ncnt = data.cnt + 1;

				// 이미 확인한 수 이거나 소수가 아니면 패스
				if (visited[npassword] == 1 || is_prime(npassword) == 0) continue;
				// 내가 찾던 그 수이면 ncnt 리턴
               			if (npassword == e) return ncnt;
               			// 확인한 수도 아니고 소수이면 큐에 삽입하여 변경 진행
				Q.push({ npassword, ncnt });
				visited[npassword] = 1;

			}
		}
	}
	printf("Impossible\n");
	return -1;
}


int main()
{
	scanf("%d", &T);
	for (int i = 0; i < T; i++) {
		scanf("%d %d", &s, &e);
		int ans = password();
		if (ans != -1) printf("%d\n", ans);
		init();
	}
	return 0;
}

응 이 문제 다시 풀어야돼... 

당연히 1000부터 9999까지 다 돌리려고 했는데 그렇게 푸는 문제 아니다. ㅋㅋㅋㅋ ㅜㅜㅠ 짱구의 한계... 

 

각설하고, 이 문제도 두 소수 사이의 변환에 필요한 "최소 횟수"를 출력해야 하기 때문에 BFS 이다. 

따라서 방문배열, 상태를 저장할 큐를 기본적으로 만들어주었다. 

 

// password( ) 함수

"현재 비밀번호와 변경할 비밀번호가 같은 경우"가 존재할 수 있다. 이때는 변경을 하지 않아도 되므로 0을 리턴해준다. 

이 문제의 경우 친절하게 이러한 예외를 테케에 포함시켜 줬지만, 그렇지 않은 더럽고 치사한 경우가 많으므로 현재 상태와 목적 상태가 같은 경우를 항상 생각해주도록 하자!

 

큐에 현재 비밀번호와 바꾼 횟수{s, 0}을 삽입하고 해당 번호를 방문처리 한다. 

큐의 모든 원소가 제거될 때 까지 루프를 돌리는데, 

1. 첫번째 for문에서는 변경할 자리값을 추출한다. 

    즉, pow가 1일때 일의자리부터 pow가 1000일때 천의자리 까지 큐에서 꺼낸 비밀번호의 자리값을 추출(del_num)하여 해당 자리를 0으로 만든다(make_zero).

예컨대 1033의 경우 pow가 1이면 일의 자리를 0으로 만든다. del_num = 3, make_zero = 1033 - (3 * 1) 

                       pow가 10이면 십의 자리를 0으로 만든다. del_num = 3, make_zero = 1033 - (3 * 10)

                       pow가 100이면 백의 자리를 0으로 만든다. del_num = 0, make_zero = 1033 - (0 * 100)

                       pow가 1000이면 천의 자리를 0으로 만든다. del_num = 1, make_zero = 1033 - (1 * 1000)

2. 두번째 for문에서는 0으로 만든 자리값에 0~9까지 대입하며(천의 자리일 경우 1~9 대입) 해당 숫자를 확인했는지 안했는지 / 소수인지 아닌지 판별한다. 

예컨대 1033의 일의 자리를 바꾸는 경우 npassword = 1030 + (0 * 1)

                                                         npassword = 1030 + (1 * 1)

                                                         npassword = 1030 + (2 * 1) .... 이런식으로 9일때 까지 돌린다. 

그리고 만약 바꾼 비밀번호가 최종 비밀번호와 같다면 ncnt를 리턴하고, 두 if문에 모두 해당되지 않을때는 큐에 담아 한 자리를 변경한 다음 비밀번호를 탐색한다. 

 

만약 while문을 다 돌 때 까지 리턴되지 않는다면 그 경우, 최종 비밀번호로 변경하지 못하는 경우이므로 Impossible을 출력한다.