BOJ 1963 - 소수경로
알고리즘/DFS∕BFS문제
https://www.acmicpc.net/problem/1963
풀이
나는 가장 먼저 이 문제는 정해진 범위의 소수만을 다루면서 여러 테이스 케이스를 입력받기 때문에 미리 소수를 판별하는 테이블을 만들어 놓았다. 그리고 현재 비밀번호와 현재 비밀번호까지 오는데 몇 번이나 거쳤는지 저장하기 위해 change라는 구조체를 만들어 <queue>에 넣고 1000의 자리부터 1의 자리까지 모두 0~9를 대입하며 큐에 넣고 방문했다는 표시를하여 다시 그 수로 돌아오지 못하게 하여 최소 경로를 찾게 하였다.
#include <cstdio> #include <cmath> #include <queue> using namespace std; struct change{ int pw,step; }; int prime[10000]={0}; int main(){ int t,i,j; double sq; scanf("%d",&t); for(i=1000;i<=9999;i++){ sq = sqrt((double)i); for(j=2;j<=sq;j++){ if(i%j==0){ prime[i] = 1; break; } } } while(t--){ int visit[10000] = {0}; queue<change> q; change chg; int from,dest,digit,rest,ans=987654321; scanf("%d%d",&from,&dest); chg.pw = from; chg.step = 0; visit[from] = 1; q.push(chg); while(!q.empty()){ if(q.front().step >= ans){ q.pop(); continue; } if(q.front().pw == dest){ ans = q.front().step; q.pop(); continue; } for(i=1;i<=1000;i*=10){ rest = q.front().pw - ((q.front().pw / i) % 10) * i; for(j=0;j<=9;j++){ if(i==1000&&!j) continue; if(prime[j*i+rest]||visit[j*i+rest]) continue; chg.pw = j*i+rest; chg.step = q.front().step + 1; q.push(chg); visit[chg.pw] = 1; } } q.pop(); } printf("%d\n",ans); } }