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

한창 완전탐색 알고리즘 문제를 풀다가 이 문제를 마주쳤는데, 계속 메모리초과가 떴다.

완전탐색은 DFS(재귀)로 풀어야 한다는 안일한 생각때문에 3일을 쓴 것 같다...ㅋㅋㅋㅋㅋ

시간 제한	메모리 제한	정답률
2초	256MB	55.583%

문제

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

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

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

입력

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

출력

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

핵심

최단경로를 구하는 문제라고 생각하면 쉽다!
당근 BFS를 이용하면 어렵지 않게 풀 수 있다.

코드

#include <iostream>
#include <algorithm>
#include <string>
#include <queue>


using namespace std;

int t;
string s1, s2;
bool is_prime[10010];
int visited[10010];

//먼저 소수를 미리 구해놓는다.
void make_prime(){
    is_prime[0] = true;
    is_prime[1] = true;
    
    for(int i=2;i*i<=10000;i++){
        if(is_prime[i]) continue;
        
        for(int j=i*i;j<=10000;j+=i){
            is_prime[j] = true;
        }
    }
    
    for(int i=0;i<=10000;i++) is_prime[i] = !is_prime[i];
}

//너비우선탐색으로 최단거리를 구한다. 이때 1000미만은 빼야하므로 주의하자.(문제 조건)
int bfs(){
    queue<string> q;
    string cur, next;
    
    q.push(s1);
    visited[stoi(s1)] = 1;
    
    while(!q.empty()){
        
        cur = q.front();
        q.pop();
        
        for(int i=0;i<4;i++){
            for(char c='0';c<='9';c++){
                if(c=='0' && i==0) continue;
                
                next = cur;
                next[i] = c;
                int snext = stoi(next);
                
                if(is_prime[snext] && visited[snext] == 0){
                    q.push(next);
                    visited[snext] = visited[stoi(cur)] + 1;
                }
            }
        }
        
        
    }
    
    //첫 시작을 1로 했으므로 마지막에 1 빼줘야 정답임.
    return visited[stoi(s2)] - 1;
}



int main(int argc, char* argv[]) {
	ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    make_prime();
    
    
    cin >> t;
    
    while(t--){
        cin >> s1 >> s2;
        
        int b = bfs();

        if(b == -1){
            cout << "Impossible\n";
        }
        else{
            cout << b << '\n';
        }
        
        //visited 배열은 재사용
        for(int i=0;i<=10000;i++){
            visited[i] = 0;
        }
    }
	
	return 0;
}