취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 1963번 문제인 소수 경로이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/1963

소수판정과 BFS를 한번에 해야 하는 문제이다.

구현력이 좋지 않다면 구현력을 높이는 데에 도움이 되는 문제인 것 같다.

글쓴이가 이 문제를 푼 방법은 다음과 같다.

1) 네 자리의 소수를 모두 찾아둔다. 이 때, Sieve of Eratosthenes(에라토스테네스의 체)를 이용하면 빠르게 소수를 찾을 수 있다.

2) 각 네 자리 소수들을 그래프의 node로 생각하자. 그리고 두 네 자리 소수가 딱 한자리만 차이날 때, 두 node 사이에 edge가 있다고 생각하자. 그러면 이 문제는 그래프 위에서 주어진 두 node 사이의 거리를 구하는 문제로 볼 수 있다.

3) 이 그래프는 weight가 없으므로, BFS를 이용하여 두 node사이 거리를 구하고, 출력한다.

이 문제를 풀면서 글쓴이는 코드가 반복되는 부분을 반복문이 아닌 코드를 복사-붙여넣기하여 해결하려는 경향이 강하다고 느꼈다.

아마 코드는 길어져도 직관적이기 때문이 아닐까 싶다.

그래도 반복 횟수가 정해져있지 않거나 큰 경우 이 방법은 사용하기 어려우니 반복문을 사용하는 습관을 길러야겠다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <string>
#include <queue>
using std::cin;
using std::cout;
using std::string;
using std::queue;

bool sieve[10000];


int main()
{
    for (int i = 2;i < 10000;i++) { // 10000 이하의 소수 탐색
        sieve[i] = true;
    }
    for (int i = 2;i < 100;i++) {
        if (sieve[i]) {
            for (int j = i * i;j < 10000;j += i) {
                sieve[j] = false;
            }
        }
    }
    int T;
    cin >> T;
    for (int i = 0;i < T;i++) { // BFS
        queue<int> que;
        bool visited[10000];
        int dist[10000];
        for (int i = 0;i < 10000;i++) {
            visited[i] = false;
            dist[i] = 0;
        }
        int x, target;
        cin >> x >> target;
        que.push(x);
        visited[x] = true;
        bool chk = false;
        while (!que.empty()) {
            int current = que.front();
            que.pop();
            int digit1 = current % 10; // 1의자리
            int digit2 = current % 100 - digit1; // 10의자리*10
            int digit3 = current % 1000 - digit2 - digit1; // 100의자리*100
            int digit4 = current - digit3 - digit2 - digit1; // 1000의자리*1000
            for (int i = 0;i < 10;i++) { // 1의자리가 다른 소수
                int num = i + digit2 + digit3 + digit4;
                if (!visited[num] and sieve[num]) {
                    que.push(num);
                    visited[num] = true;
                    dist[num] = dist[current] + 1;
                    if (num == target) chk = true;
                }
            }
            if (chk) break;
            for (int i = 0;i < 10;i++) { // 10의자리가 다른 소수
                int num = digit1 + 10 * i + digit3 + digit4;
                if (!visited[num] and sieve[num]) {
                    que.push(num);
                    visited[num] = true;
                    dist[num] = dist[current] + 1;
                    if (num == target) chk = true;
                }
            }
            if (chk) break;
            for (int i = 0;i < 10;i++) { // 100의자리가 다른 소수
                int num = digit1 + digit2 + 100 * i + digit4;
                if (!visited[num] and sieve[num]) {
                    que.push(num);
                    visited[num] = true;
                    dist[num] = dist[current] + 1;
                    if (num == target) chk = true;
                }
            }
            if (chk) break;
            for (int i = 1;i < 10;i++) { // 1000의자리가 다른 소수: 1000의자리가 0이 되면 안됨에 유의
                int num = digit1 + digit2 + digit3 + 1000 * i;
                if (!visited[num] and sieve[num]) {
                    que.push(num);
                    visited[num] = true;
                    dist[num] = dist[current] + 1;
                    if (num == target) chk = true;
                }
            }
            if (chk) break;
        }
        cout << dist[target]<<'\n';
    }

    return 0;
}