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

github : https://github.com/junho0956/Algorithm/blob/master/1963/1963/%EC%86%8C%EC%8A%A4.cpp

 

BFS 로 구현하였습니다.

소수는 아래 코드와 같이 에라토스테네스의 체에 대한 기본개념을 알고 있으면 충분하고

소수를 전부 구해낸 후에,

1자리씩 비교하면서 모든 소수와 비교하여 BFS 로 탐색하였습니다.

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
 
int testcase, N, K;
int sosu[10001];
bool visit[10001];
vector<int> v;
queue<pair<int, int> > q;
 
bool checking(int vnum, int num) {
 
    int cnt = 0;
 
    int check_vnum = vnum;
    int check_num = num;
 
    while (check_num) {
        if (check_num % 10 == check_vnum % 10) cnt++;
        check_num /= 10, check_vnum /= 10;
    }
 
    if (cnt == 3) return true;
    else return false;
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
 
    for (int i = 0; i < 10001; i++) sosu[i] = true;
 
    for (int i = 2; i * i < 10001; i++) {
        if (!sosu[i]) continue;
        for (int k = i * i; k < 10001; k += i) sosu[k] = 0;
    }
 
    for (int i = 1000; i < 10001; i++) if (sosu[i]) v.push_back(i);
 
    cin >> testcase;
    while (testcase--) {
        for (int i = 1000; i < 10001; i++) visit[i] = 0;
        
        cin >> N >> K;
        q.push({ N,0 });
        while (!q.empty()) {
            int now = q.front().first;
            int cnt = q.front().second;
            q.pop();
 
            if (visit[now]) continue;
            visit[now] = 1;
 
            if (now == K) {
                cout << cnt << '\n';
                while (!q.empty()) q.pop();
            }
 
            for (int i = 0; i < v.size(); i++) {
                if (checking(v[i], now)) q.push({ v[i],cnt + 1 });
            }
        }
    }
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

BOJ 1525번 퍼즐  (0) 2020.01.24
BOJ 9019번 DSLR  (0) 2020.01.23
BOJ 13913번 숨바꼭질4  (0) 2020.01.23
BOJ 13549번 숨바꼭질3  (0) 2020.01.22
BOJ 12851번 숨바꼭질2  (0) 2020.01.22

BOJ : https://www.acmicpc.net/problem/13913

github : https://github.com/junho0956/Algorithm/blob/master/13913/13913/%EC%86%8C%EC%8A%A4.cpp

 

BFS 의 특성상

처음 방문한 곳은 다시 방문할 필요가 없어진다.

이를 이용한다면

방문배열뿐만 아니라 이 정점(숫자)을 방문하기 직전의 정점을 기억할 배열을 따로 만들어둔다면

이 배열 역시 단 한번만 방문하면 되기 때문에 이 정점을 방문하기 직전의 정점만 저장해두면 

쉽게 문제를 해결할 수 있다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <iostream>
#include <queue>
#include <vector>
#include <stack>
using namespace std;
 
int N, K;
int btk[100001];
queue<pair<int, int> > q;
bool visit[100001];
 
int main() {
    cin >> N >> K;
 
    for (int i = 0; i <= 100000; i++) btk[i] = -1;
 
    int Min = 999999;
    btk[N] = N;
 
    q.push({ N,0 });
    while (!q.empty()) {
        int now = q.front().first;
        int cnt = q.front().second;
        q.pop();
 
        if (now > 100000 || now < 0) continue;
 
        if (visit[now]) continue;
        visit[now] = true;
 
        if (cnt > Min) continue;
        if (now == K) {
            Min = cnt;
            break;
        }
 
        if (now != 0 && now < K && now * 2 <= 100000) {
            q.push({ now * 2, cnt + 1 });
            if (btk[now * 2] == -1) btk[now * 2] = now;
        }
        if (now - 1 >= 0) {
            q.push({ now - 1,cnt + 1 });
            if (btk[now - 1] == -1) btk[now - 1] = now;
        }
        if (now + 1 <= 100000) {
            q.push({ now + 1,cnt + 1 });
            if (btk[now + 1] == -1) btk[now + 1] = now;
        }
    }
 
    stack<int> s;
    int back_check = K;
    s.push(K);
    while (1) {
        if (btk[back_check] != back_check) {
            s.push(btk[back_check]);
            back_check = btk[back_check];
        }
        else break;
    }
 
    cout << Min << endl;
    while (!s.empty()) {
        int num = s.top();
        s.pop();
        cout << num << ' ';
    }
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

BOJ 9019번 DSLR  (0) 2020.01.23
BOJ 1963번 소수 경로  (0) 2020.01.23
BOJ 13549번 숨바꼭질3  (0) 2020.01.22
BOJ 12851번 숨바꼭질2  (0) 2020.01.22
BOJ 1697번 숨바꼭질  (0) 2020.01.22

BOJ : https://www.acmicpc.net/problem/13549

github : https://github.com/junho0956/Algorithm/blob/master/13549/13549/%EC%86%8C%EC%8A%A4.cpp

 

숨바꼭질 문제 자체를 BFS 로 접근해야 하는 이유를 정확히 파악해보자면

가장 작은 간선(횟수)들로만 계속해서 연결해나가야 하기 때문에

현재 사용할 주어진 간선의 가중치가 동일하다는 전제조건이 있는 BFS 를 사용해야한다. 입니다

 

숨바꼭질3을 queue를 이용한 단순한 BFS 로 해결할 수 있을까? 에 대한 질문이 있다면

이 문제 자체는 문제의 특성 때문에 조건문만 잘 써준다면 우연히도 맞출 수 있게 됩니다.

그 우연한 조건이 *2 를 하고나서 +1 -1 순서로 queue 에 넣는것이 아닌 -1 +1 순서로 queue에 넣는 이유입니다.

어떤 경우에 +1 -1 이 오답처리가 되는지는 잘 모르겠습니다.

 

숨바꼭질3 같은 경우 *2 를 할때 간선(횟수)의 가중치가 0이 되게 됩니다.

BFS 를 하게 되면 다음으로 큰 가중치를 가진 간선을 push 하면서 맨뒤로 보내게 되는 과정을 알고 계실겁니다.

하지만 가중치가 0인 간선을 queue의 맨뒤로 보내면 이건 BFS 라고 할 수 없게 됩니다.

 

이 조건을 이용한다면 문제를 해결할 수 있게 됩니다.

가중치가 0인 간선을 queue의 back 이 아닌 front에 삽입할려면

list 형태의 queue 인 deque 를 이용하여 문제를 해결할 수 있게 됩니다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
#include <deque>
using namespace std;
 
int N, K;
deque<pair<int, int> > q;
bool visit[100001];
 
int main() {
    cin >> N >> K;
 
    int Min = 999999;
    q.push_back({ N,0 });
    while (!q.empty()) {
        int now = q.front().first;
        int cnt = q.front().second;
        q.pop_front();
 
        if (now > 100000 || now < 0) continue;
 
        if (visit[now]) continue;
        visit[now] = true;
 
        if (cnt > Min) continue;
        if (now == K) {
            Min = cnt;
            continue;
        }
 
        if (now != 0 && now < K) q.push_front({ now * 2, cnt });
        q.push_back({ now + 1,cnt + 1 });
        q.push_back({ now - 1,cnt + 1 });
    }
 
    cout << Min;
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

BOJ 1963번 소수 경로  (0) 2020.01.23
BOJ 13913번 숨바꼭질4  (0) 2020.01.23
BOJ 12851번 숨바꼭질2  (0) 2020.01.22
BOJ 1697번 숨바꼭질  (0) 2020.01.22
BOJ 10819번 차이를 최대로  (0) 2020.01.22

BOJ : https://www.acmicpc.net/problem/12851

github : https://github.com/junho0956/Algorithm/blob/master/12851/12851/%EC%86%8C%EC%8A%A4.cpp

 

이 문제를 해결할 수 있는 방법은 2가지가 있을 것 같습니다.

1. 가장 정확한 방법

숨바꼭질(1697번) 문제를 생각해보면

큐에서 넣는 3가지 작업을 거치기 전에 방문배열을 확인해서 이미 방문했으면 패스하는 조건을 쓰게 됩니다.

하지만 이 경우 임의의 수가 *2, +1, -1 의 작업을 했을 때 같은 값을 가지게 된다면?

한가지 조건만 사용하게 되고 나머지는 사용하지 않게 될 것입니다.

숨바꼭질2 의 중요포인트는 이 부분이고, 이 부분을 해결하기 위해서는

큐에서 꺼낸 후에 pop 을 하면서 방문처리를 해주는 것+방문확인은 안하는 것 입니다.

 

좀더 정확히 말하자면 지금 사용할 값을 바로 방문처리 해주는 것입니다.

예를 들면 1->4 를 만들기 위해서는 

1 -> 2(+1) -> 4

1 -> 2(*2) -> 4

이 2가지 방법을 사용해야하고,

만약 큐에서 2를 꺼냈는데 방문을 확인해버리게 되면 +1 또는 *2 중 1개를 확인하게 되고

다음 큐에서 2를 꺼냈을 때는 방문한 것으로 확인하고 넘어가버리게 되서 나머지 1개를 확인하지 못하게 됩니다.

 

그러므로 2를 꺼내서 바로 방문처리를 해주고 확인은 하지않는다면? 

=> 2(+1)을 먼저 꺼냈다고 해도 큐에는 아직 2(*2) 가 남아있고

다음에 2(*2) 를 꺼내도 이미 방문은 했지만 확인은 하지 않으니 2(*2) 도 사용할 수 있게 되는 것입니다.

 

 

2. 편법을 통해서.. 문제를 해결할 수 있습니다.

애초에 어떤 임의의 수를 만들 수 있는 방법은 *2, +1, -1 이 있으니

아무리 많아도 3가지 일 것입니다.

방문배열을 체크만 하는 것이 아닌, 몆번 방문했는지 확인한다면

3번 을 초과해서 방문할 일은 없어집니다.

 

if (visit[now] > 3) continue;

visit[now]++;

 

의 코드를 사용한다면.. 1번 방법을 모르더라도 10만정도의 범위를 해결하는데는 무리가 없습니다 ㅎㅎ...

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
#include <queue>
using namespace std;
 
int N, K, check;
queue<pair<int, int> > q;
int visit[100001];
 
int main() {
    cin >> N >> K;
 
    int Min = 999999;
    q.push({ N,0 });
    while (!q.empty()) {
        int now = q.front().first;
        int cnt = q.front().second;
        q.pop();
 
        if (now > 100000 || now < 0) continue;
 
        if (cnt > Min) continue;
        if (now == K) {
            Min = cnt;
            check++;
            continue;
        }
 
        if (visit[now] > 3) continue;
        visit[now]++;
 
        if (now != 0 && now < K) q.push({ now * 2, cnt + 1 });
        q.push({ now + 1,cnt + 1 });
        q.push({ now - 1,cnt + 1 });
    }
 
    cout << Min << '\n' << check;
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

BOJ 13913번 숨바꼭질4  (0) 2020.01.23
BOJ 13549번 숨바꼭질3  (0) 2020.01.22
BOJ 1697번 숨바꼭질  (0) 2020.01.22
BOJ 10819번 차이를 최대로  (0) 2020.01.22
BOJ 2410번 2의 멱수의 합  (0) 2020.01.22

+ Recent posts

티스토리툴바