BOJ 1963 소수 경로(C++)

소수 경로 성공

한국어원문

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	1564	791	549	53.249%

문제

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

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

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

입력

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

출력

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

예제 입력 

3
1033 8179
1373 8017
1033 1033

예제 출력 

6
7
0

힌트

출처

ACM-ICPC > Regionals > Europe > Northwestern European Regional Contest > NWERC 2006 G번

• 문제의 오타를 찾은 사람: waylight3

링크

• ACM-ICPC Live Archive
• PKU Judge Online
• TJU Online Judge
• Sphere Online Judge
• HDU Online Judge

알고리즘 분류

• BFS
• 소수

#include    <cstdio>
#include    <cmath>
#pragma warning(disable:4996)
 
int P[11111];
int visit[11111];
int queue[9999];
int rear, front;
int main()
{
 
    for (int i = 2; i <= 100; ++i)
    if (P[i] == 0)
    for (int j = i*i; j <= 10000; j += i)
        P[j] = 1;
 
 
    int TC;
    int S, E;
    scanf("%d", &TC);
    for (int t = 1; t <= TC; ++t)
    {
        int res = -1;
        scanf("%d%d", &S, &E);
        for (int i = 1000; i <= 9999; ++i) //초기화
            visit[i] = -1;
 
        front = rear = 1;
        queue[rear++] = S;
        visit[S] = 0;
 
        while (front < rear)
        {
            int num = queue[front++];
            if (num == E)
                break;
 
            int n1, n2, n3, n4;
            n1 = num / 1000 * 1000; n2 = num % 1000 / 100 * 100; n3 = num % 100 / 10 * 10; n4 = num % 10;
            for (int i = 0; i <= 9; ++i)
            {
                if (visit[n1 + n2 + n3 + i] == -1 && P[n1 + n2 + n3 + i] == 0)
                {
                    queue[rear++] = n1 + n2 + n3 + i;
                    visit[n1 + n2 + n3 + i] = visit[num] + 1;
                }
                if (visit[n1 + n2 + i * 10 + n4] == -1 && P[n1 + n2 + i * 10 + n4] == 0)
                {
                    queue[rear++] = n1 + n2 + i * 10 + n4;
                    visit[n1 + n2 + i * 10 + n4] = visit[num] + 1;
                }
                if (visit[n1 + i * 100 + n3 + n4] == -1 && P[n1 + i * 100 + n3 + n4] == 0)
                {
                    queue[rear++] = n1 + i * 100 + n3 + n4;
                    visit[n1 + i * 100 + n3 + n4] = visit[num] + 1;
                }
                if (i == 0)
                    continue;
                if (visit[i * 1000 + n2 + n3 + n4] == -1 && P[i * 1000 + n2 + n3 + n4] == 0)
                {
                    queue[rear++] = i * 1000 + n2 + n3 + n4;
                    visit[i * 1000 + n2 + n3 + n4] = visit[num] + 1;
                }
            }
        }
 
        if (visit[E] == -1)
            printf("Impossible\n");
        else
            printf("%d\n", visit[E]);
    }
 
    return 0;
}

전형적인 BFS문제였다. 

장기나 엘레베이터 같은 문제였지만 소수구하기가 포함되어있어 약간 더 풀기에 재미있었던(?) 문제였다. 

우선 소수를 구한다. 소수를 구하는 공식은 에라토스테네스의 체라는 유명한 방법이 있으므로 넘어간다. 

4자리 수 이므로 1000~9999사이의 수이다. 

4개로 나누어 주었다. 1000의 자리, 100의 자리, 10의 자리, 1의 자리. 

이것을 0~9까지 돌면서 소수이고 방문하지 않은 수를 queue에 넣어주며 visit에 몇번 변환해야 바뀔 수 있는지 넣어주었다. 

(방문과 동시에 횟수까지 처리하기 위함)

주의해야 할 점은 1000의 자리는 0이 되면 안되기 때문에 57~8라인에서 i가 0인 경우 아래쪽은 실행하지 않았다는 것이다. 

그외에는 어렵지 않았다.