완전탐색 - BFS (숨바꼭질 1697번 , 소수 경로 - 1963번 , DSLR

완전탐색 - BFS (숨바꼭질 1697번 , 소수 경로 - 1963번 , DSLR - 9019번)

띠그랭 2018. 4. 3. 14:38

2018. 4. 3. 14:38

완전탐색 - BFS(큐를 이용하여 풀기 , 숨바꼭질 - 1697번 , 소수 경로 - 1963번 , DSLR - 9019번)

BFS를 이용하여 문제를 푼다는 것은 그래프에서 최단,최소의 경로를 구하는 문제

이 때 조건은 A -> B 로 가는 간선의 가중치가 모두 동일하거나, 1이 여야 한다.

문제를 풀어서 BFS를 느껴보자.

1) 숨바꼭질 - 1697번

https://www.acmicpc.net/problem/1697

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

예제 입력

 
xxxxxxxxxx
5 17

예제 출력

소스 코드

 
xxxxxxxxxx
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
int BFS(int start, int end)
{
    queue<pair<int,int>> q;
    q.push({start, 0});
    int check[100001] = { 0 };
    check[start] = 1;
    while (1)
    {
        if (q.empty() || q.front().first == end) {
            return q.front().second;
            break;
        }
        int pos = q.front().first;
        int seq = q.front().second;
        q.pop();
        if (pos - 1 >= 0 && !check[pos - 1])
        {
            q.push({ pos - 1 , seq + 1 });
            check[pos - 1] = 1;
        }
        if (pos + 1 <= 100000 && !check[pos + 1])
        {
            q.push({ pos + 1 , seq + 1 });
            check[pos + 1] = 1;
        }
        if (pos * 2 <= 100000 && !check[pos * 2])
        {
            q.push({ pos * 2 , seq + 1 });
            check[pos * 2] = 1;
        }
    }
}
int main()
{
    int s, e;
    cin >> s >> e;
    int res = BFS(s, e);
    cout << res << '\n';
    return 0;
}

2) 소수 경로 - 1963번

https://www.acmicpc.net/problem/1963

문제

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

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

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

입력

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

출력

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

예제 입력

 
xxxxxxxxxx
3
1033 8179
1373 8017
1033 1033

예제 출력

 
xxxxxxxxxx
6
7
0

소스 코드

 
xxxxxxxxxx
#include<iostream>
#include<queue>
#include<algorithm>
#include<string>
using namespace std;
int sosu[10000];
int change(int n, int i, int j)
{
    string num;
    num = to_string(n);
    num[i] = j + '0';
    return stoi(num);
}
int BFS(int start, int end)
{
    queue<pair<int, int>>q;
    q.push({ start , 0 });
    int chk[10000] = { 0 };
    while (1)
    {
        if (q.empty() || q.front().first == end)
            return q.front().second;
        int pos = q.front().first;
        int seq = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++)
        {
            for (int j = 0; j < 10; j++)
            {
                int tmp = change(pos, i, j);
                if (sosu[tmp] && !chk[tmp])
                {
                    q.push({tmp, seq + 1});
                    chk[tmp] = 1;
                }
            }
        }
    }
}
int main()
{
    int t;
    int s, e;
    cin >> t;
    for (int i = 2; i <= 9999; i++)
        sosu[i] = i;
    for (int i = 2; i <= 9999; i++)
    {
        if (!sosu[i]) continue;
        for (int j = i * 2; j <= 9999; j += i)
            sosu[j] = 0;
    }
    for (int i = 2; i <= 999; i++)
        sosu[i] = 0;
    for (int i = 0; i < t; i++)
    {
        cin >> s >> e;
        cout << BFS(s, e) << '\n';
    }
    return 0;
}

3) DSLR - 9019번

https://www.acmicpc.net/problem/9019

문제

네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 저장된 n을 다음과 같이 변환한다. n의 네 자릿수를 d1, d2, d3, d4라고 하자(즉 n = ((d1 × 10 + d2) × 10 + d3) × 10 + d4라고 하자)

D: D 는 n을 두 배로 바꾼다. 결과 값이 9999 보다 큰 경우에는 10000 으로 나눈 나머지를 취한다. 그 결과 값(2n mod 10000)을 레지스터에 저장한다.
S: S 는 n에서 1 을 뺀 결과 n-1을 레지스터에 저장한다. n이 0 이라면 9999 가 대신 레지스터에 저장된다.
L: L 은 n의 각 자릿수를 왼편으로 회전시켜 그 결과를 레지스터에 저장한다. 이 연산이 끝나면 레지스터에 저장된 네 자릿수는 왼편부터 d2, d3, d4, d1이 된다.
R: R 은 n의 각 자릿수를 오른편으로 회전시켜 그 결과를 레지스터에 저장한다. 이 연산이 끝나면 레지스터에 저장된 네 자릿수는 왼편부터 d4, d1, d2, d3이 된다.

위에서 언급한 것처럼, L 과 R 명령어는 십진 자릿수를 가정하고 연산을 수행한다. 예를 들어서 n = 1234 라면 여기에 L 을 적용하면 2341 이 되고 R 을 적용하면 4123 이 된다.

여러분이 작성할 프로그램은 주어진 서로 다른 두 정수 A와 B(A ≠ B)에 대하여 A를 B로 바꾸는 최소한의 명령어를 생성하는 프로그램이다. 예를 들어서 A = 1234, B = 3412 라면 다음과 같이 두 개의 명령어를 적용하면 A를 B로 변환할 수 있다.

1234 →L 2341 →L 3412 1234 →R 4123 →R 3412

따라서 여러분의 프로그램은 이 경우에 LL 이나 RR 을 출력해야 한다.

n의 자릿수로 0 이 포함된 경우에 주의해야 한다. 예를 들어서 1000 에 L 을 적용하면 0001 이 되므로 결과는 1 이 된다. 그러나 R 을 적용하면 0100 이 되므로 결과는 100 이 된다.

입력

프로그램 입력은 T 개의 테스트 케이스로 구성된다. 테스트 케이스 개수 T 는 입력의 첫 줄에 주어진다. 각 테스트 케이스로는 두 개의 정수 A와 B(A ≠ B)가 공백으로 분리되어 차례로 주어지는데 A는 레지스터의 초기 값을 나타내고 B는 최종 값을 나타낸다. A 와 B는 모두 0 이상 10,000 미만이다.

출력

A에서 B로 변환하기 위해 필요한 최소한의 명령어 나열을 출력한다.

예제 입력

 
xxxxxxxxxx
3
1234 3412
1000 1
1 16

예제 출력

 
xxxxxxxxxx
LL
L
DDDD

소스 코드

 
xxxxxxxxxx
#include <iostream>
#include <queue>
#include<string>
using namespace std;
// 9019
int main() {
    int n;
    cin >> n;
    while (n-- > 0) {
        int start, end;
        cin >> start >> end;
        bool check[20000] = {false};
        string dist[10000];
        check[start] = true;
        queue<int> q;
        q.push(start);
        while (!q.empty()) {
            int x = q.front();
            q.pop();
            int next = (x * 2) % 10000;
            if (!check[next]) {
                q.push(next);
                dist[next] = dist[x] + 'D';
                check[next] = true;
            }
            next = x > 0 ? x - 1 : 9999;
            if (!check[next]) {
                q.push(next);
                dist[next] = dist[x] + 'S';
                check[next] = true;
            }
            int top = x / 1000;
            next = (x % 1000) * 10 + top;
            if (!check[next]) {
                q.push(next);
                dist[next] = dist[x] + 'L';
                check[next] = true;
            }
            int bottom = x % 10;
            next = (x / 10) + (bottom * 1000);
            if (!check[next]) {
                q.push(next);
                dist[next] = dist[x] + 'R';
                check[next] = true;
            }
        }
        cout << dist[end] << '\n';
    }
    return 0;
}

'알고리즘 > 완전탐색' 카테고리의 다른 글

삼성 코딩 테스트 기출 - 로봇청소기 14503번 (단순구현) 완탐X (0)	2018.04.04
삼성 코딩 테스트 기출 - 연구소 14502번 (DFS, BFS) (0)	2018.04.04
완전탐색 - 순열 응용편 (차이를 최대로 - 10819번 , 외판원 순회 2 - 10971번 , 로또 - 6603번) (0)	2018.04.02
완전탐색 - 순열 기초 (0)	2018.04.02
완전탐색 - Brute Force Search (0)	2018.04.02

띠그랭