문제풀이/백준
[C++] 백준 - 1963 : 소수 경로
orubt
2021. 1. 15. 09:21
반응형
1963번: 소수 경로
소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금
www.acmicpc.net
풀이 )
현재 입력받은 수에 대해서 한 자리씩 숫자를 하나씩 바꿔가면서 BFS를 한다.
같은 수를 다시 Queue에 넣는 것을 방지하기 위해 visited 배열을 사용하여 방문 여부를 확인하여 방문한 경우 Queue에 넣지 않는다.
한 자리씩 바꾸는 경우 현재 수 num, 자릿수 digit, 바꾸자하는 수 i를 매개변수로 받아 결과값을 반환하는 make( )를 만들었다. (제곱을 구하는 pow( )에서는 밑을 10으로 고정하여 지수만 입력받아 반환하도록 했다.)
ex ) 1234에서 10^2의 자리수 2를 7로 바꾼다하면 make(1234, 2, 7)을 호출한다.
1734바꾸면 되므로
- 10^2보다 큰 자리에 대해선 그대로 두기 위해 num/pow(digit+1)*pow(digit+1)
- 10^2자리에서는 pow(digit)*i
- 10^2이하 자리에서는 num%pow(digit);
#include <iostream>
#include <queue>
#include <utility>
using namespace std;
bool prime[10000];
int pow(int num){
if(!num)
return 1;
return 10*pow(num-1);
}
int make(int num, int digit, int i){
return (num/pow(digit+1)*10+i)*pow(digit)+num%pow(digit);
}
int main(void){
for(int i = 1000; i < 10000; ++i){
prime[i] = true;
for(int j = 2; j < 100; ++j){
if(i%j==0){
prime[i] = false;
break;
}
}
}
int t;
cin >> t;
int a, b;
while(t--){
cin >> a >> b;
queue<pair<int, int> > q; // 숫자, 단계
bool visited[10000] = {false, };
q.push({a, 0});
visited[a] = true;
while(1){
int tmp = q.front().first;
int cnt = q.front().second;
if(tmp == b){
cout << cnt << '\n';
break;
}
visited[tmp] = true;
q.pop();
for(int digit = 0; digit < 4; ++digit){
for(int i = 0; i < 10; ++i){
if(digit == 3 && i == 0)
continue;
a = make(tmp, digit, i);
if(visited[a] || !prime[a])
continue;
q.push({a, cnt+1});
}
}
}
}
}
반응형