백준 1963 소수 경로

1. 문제 정리

  - 비밀번호는 4자리이며, 소수이다.

  - 비밀번호는 한번에 한자리만 바꿀 수 있다.

  - 비밀번호는 4자리 수로, 1000 이상 9999이하이다.

  - 비밀번호 A에서 새로운 비밀번호 B로 바꾸기 위한 최소 변경 횟수를 구하라.

  - 변경할 수 없다면 Impossible을 출력하라.

 

2. 접근

  - 비밀번호는 소수이므로 소수 판정을 필요로 한다. 에라토스테네스의 체를 이용하자.

  - 네자리 값을 모두 판별하기 위해 탐색을 해야한다. Brute Force를 BFS를 이용해 풀어나가자.

  - 시간 복잡도는 모든 가능한 경우의 수를 탐색하는 것으로 O(n) = O(10000)으로 제한시간인 2초 안에 문제를 풀 수 있다.

 

3. 풀이

#include<iostream>
#include<queue>
using namespace  std;

bool check[10000];
int dist[10000];

void init(){
    check[0] = check[1] = true;
    for (int i = 2; i < 10000; i++) check[i] = true;
	
	for (int i = 2; i * i < 10000; i++) {
		for (int k = i * i; k < 10000; k += i) {
			check[k] = false;
		}
	}
}

int toInt(string num){
    int ret = 0;
    for(int i = 0; i < 4; i++){
        ret = ret * 10 + (num[i] -'0');
    }
    return ret;
}

bool isPossible(int num){
    if(num < 1000 || num > 9999) return false;
    return true;
}

int bfs(int start, int dest){
    queue<int> q;
    q.push(start);
    dist[start] = 0;
    while(!q.empty()){
        int node = q.front(); q.pop();
        if(node == dest) return dist[node];
        for(int i = 0; i < 4; i++){
            string node_s = to_string(node);
            for(int j = 0; j < 10; j++){
                node_s[i] = j + '0';
                int next = toInt(node_s);
                if(check[next] && dist[next] == -1 && next > 999){
                    dist[next] = dist[node]+1;
                    q.push(next);
                }
            }
        }
    }
    return -1;
}

int main(){
    int T;
    int start, dest;
    init();
    cin >> T;
    for(int i = 0; i < T; i++){
        cin >> start >> dest;
        for(int j = 0; j < 10000; j++) dist[j] = -1;
        int result = bfs(start, dest);
        if(result == -1) cout << "Impossible" << '\n';
        else cout << result << '\n';
    }
}

  - init()에서 아리스토테네스의 체를 이용하여 999와 10000 사이의 모든 소수 값을 판별해둔다.

  - toInt() string으로 되어있는 네자리의 수를 int 타입의 네자리 수로 바꾼 후 반환한다.

  - isPossible()으로 판별하는 값이 유효한 값인지(999와 10000 사이의 값인지) 판별하여 아닐 경우 false, 유효할 경우 true를 반환한다.

  - bfs()으로 탐색을 한다. 탐색은 위 toInt(), isPossible() 함수를 이용하며, for(i)를 통해 바꿀 자릿수를 선택하고 for(j)를 통해 선택된 자릿수의 값을 1 이상 9 이하의 값으로 바꾼다. 이후 검사해보지 않았던 값에 대해 해당 값까지 변화하는데 필요했던 변화 횟수를 dist배열에 기록하고 q에 해당 네자리값을 push 한다.

    이후 bfs()의 while loop이 끝나기 전에, 변경하려고 하는 비밀번호 값에 도달하게 되었을 경우 해당 함수를 종료하며 dist[변경하려고 한 비밀번호]를 반환한다. 그러지 못하고 q에 더 이상 넣을 값이 없어져 while loop가 종료되었을 경우에는 -1을 반환하여 비밀번호를 변경할 수 없음을 알린다.

  - main()에서 bfs를 실행하여 얻은 반환값을 통해 -1인 경우 Impossible을, 그 외의 경우 반환값을 출력하고 프로세스를 종료한다.

 

4. 소감

  이번 문제는 처음 봤을 때 bfs로 풀 수 있을까 라는 생각을 못 했던 것 같다. 아직까지도 bfs라면 그래프를 이용해서, 또는 여러 배열을 이용해서 문제를 푸는 정형화된 방식만 생각하고, 그것에 익숙해 졌었는데 이번 문제를 풀면서 bfs로 풀 수 있는 문제는 좀 더 다양하다는 것을 깨달았다.

 또한 앞으로 더 다양한 문제를 접하여 문제에 접근하는 시야를 넓혀야 겠다는 생각도 할 수 있어 좋은 문제였다고 생각한다.