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

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

 

퍼즐은 내 초보적 지식으로는 해결하는데 어려움이 있는 문제였다.

 

숫자가 9개가 주어진다는 점에서 3*3 배열을 사용하는 것이 아닌

9개를 나열한 int형 수를 사용하면 된다는 점까지는 접근하였다.

 

하지만 이 정보가지고는 BFS 를 돌리는데 문제가 있었다.

9자리 int형이면 정말 가능한 모든 범위는 987654321 까지는 봐야한다는 점인데,

이걸 방문배열을 통해서 확인하려고 하니

저정도의 큰 크기를 가진 배열을 사용할수도 없고,

그렇다고 만들어진 수를 이용해서 이분탐색으로 찾아볼려니

매번 정렬해야한다는 단점이 있어서 시간초과를 어떤식으로 해결해야할지 접근을 못했었다.

 

그러다가 알게된 방법이 set , map 이라는 STL 템플릿이였고,

이중에서 set 을 사용하였다.

set 을 아직 공부를 하지않아 정확한 개념을 모르지만, 어떤 값에 대한 유무를 판별하는데 사용된다고 한다.

내부 구현을 몰라서 뭐 어떤식으로 값에 대한 유무 판단을 하는 것인지는 모르겠지만

일단 사용해보았는데? 정말 빨랐다.

디버깅을 해보았는데 살짝 Heap 같이 원소를 넣을때마다 자동정렬이 되는 것을 확인하였다.

 

조만간 set의 내부구현, 작동원리에 대해서 공부하여 포스팅하는 시간을 가져보도록 해야겠다.

 

이 문제의 핵심은,

3*3 배열을 사용하는 것이 아닌, 9자리 int 형 숫자를 이용하여

완전탐색 식의 BFS 을 통해 문제를 해결하는 것이고

 

주의할 점은, 0이 아닌 9를 사용해야한다는점 ( 위에서도 설명했다 )

맨 왼쪽, 맨 오른쪽은 -1, +1 에 의한 변경이 안된다는 점만 주의하면 된다.

 

 

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
#include <iostream>
#include <string>
#include <queue>
#include <algorithm>
#include <set>
using namespace std;
 
string ans = "123456789";
queue<pair<string, int> > q;
set<int> visit;
 
bool check_visit(string str) {
    int key = stoi(str);
    
    if (visit.find(key) != visit.end()) return false;
    else return true;
}
 
void changing(string change, int index, int cnt, int location) {
    if (location +index >= 0 && location + index < 9) {
 
        if (location % 3 == 1 || (location % 3 == 2 && index != 1) || (location % 3 == 0 && index != -1)) {
            swap(change[location], change[location + index]);
            if (check_visit(change)) q.push({ change,cnt + 1 }), visit.insert(stoi(change));
        }
    }
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
 
    int n;
    string str;
    bool solve = false;
 
    for (int i = 0; i < 9; i++) {
        cin >> n;
        if (n == 0) n = 9;
        str.push_back(n+'0');
    }
    
    q.push({ str,0 });
    while (!q.empty()) {
        string check = q.front().first;
        int cnt = q.front().second;
        q.pop();
 
        if (check.compare(ans) == 0) {
            cout << cnt;
            solve = true;
            break;
        }
        int location = check.find('9');
        
        changing(check, -3, cnt, location);
        changing(check, 3, cnt, location);
        changing(check, -1, cnt, location);
        changing(check, 1, cnt, location);
    }
 
    if (!solve) cout << "-1";
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

 

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

BOJ 2186번 문자판  (0) 2020.01.27
BOJ 2251번 물통  (0) 2020.01.24
BOJ 9019번 DSLR  (0) 2020.01.23
BOJ 1963번 소수 경로  (0) 2020.01.23
BOJ 13913번 숨바꼭질4  (0) 2020.01.23

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

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

 

문제에서 요구하는 그대로 작성하였다.

코드를 정확히 하지않으면 1000 같은 숫자는 L 했을 때 1 이 되고 R 했을 때 100 이 되는 경우들에 대한

반례가 분명 생길 것 같아서

어차피 4자리 숫자이니 한자리씩 가지고 와서 체크후, 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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include <iostream>
#include <queue>
#include <stack>
using namespace std;
 
// 한자리씩 가지고오기 위한 구조체
typedef struct number {
    int init[4];
};
number result;
 
// 어떤 명령어를 사용했는지 체크하기 위한 배열
pair<char, int> parent[10000];
bool visit[10000];
int Testcase, A, B, now;
queue<int> q;
stack<char> s;
 
void now_check(int num) {
 
    for (int i = 0; i < 4; i++) result.init[i] = 0;
 
    int idx = 3;
    while (num) {
        result.init[idx--] = num % 10;
        num /= 10;
    }
}
 
void D() {
    int temp = result.init[0];
    for (int i = 1; i < 4; i++) {
        temp = temp * 10 + result.init[i];
    }
 
    temp = (temp * 2) % 10000;
    if (!visit[temp] && parent[temp].first == NULL) {
        parent[temp].first = 'D';
        parent[temp].second = now;
        q.push(temp);
    }
}
 
void S() {
    int temp = result.init[0];
    for (int i = 1; i < 4; i++) {
        temp = temp * 10 + result.init[i];
    }
 
    if (temp == 0) temp = 9999;
    else temp--;
 
    if (!visit[temp] && parent[temp].first == NULL) {
        parent[temp].first = 'S';
        parent[temp].second = now;
        q.push(temp);
    }
}
 
void L() {
    int temp = result.init[1];
    temp = temp * 10 + result.init[2];
    temp = temp * 10 + result.init[3];
    temp = temp * 10 + result.init[0];
 
    if (!visit[temp] && parent[temp].first == NULL) {
        parent[temp].first = 'L';
        parent[temp].second = now;
        q.push(temp);
    }
}
 
void R() {
    int temp = result.init[3];
    temp = temp * 10 + result.init[0];
    temp = temp * 10 + result.init[1];
    temp = temp * 10 + result.init[2];
 
    if (!visit[temp] && parent[temp].first == NULL) {
        parent[temp].first = 'R';
        parent[temp].second = now;
        q.push(temp);
    }
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
 
    cin >> Testcase;
    while (Testcase--) {
        for (int i = 0; i < 10000; i++) parent[i].first = NULL;
        for (int i = 0; i < 10000; i++) visit[i] = 0;
 
        cin >> A >> B;
        q.push(A);
 
        while (!q.empty()) {
            now = q.front();
            q.pop();
 
            if (visit[now]) continue;
            visit[now] = true;
            
            if (now == B) {
                while (!q.empty()) q.pop();
                break;
            }
// now_check 를 통해서 구조체에 한자리씩 저장해둔다
            now_check(now);
// 주어진 조건에 맞게 함수내에서 q push
            D(), S(), L(), R();
        }
 
        int temp = B;
// 부모를 따라가는 과정
        while (parent[temp].first != NULL) {
            s.push(parent[temp].first);
            temp = parent[temp].second;
        }
        while (!s.empty()) {
            cout << s.top();
            s.pop();
        }
        cout << '\n';
    }
 
    return 0;
}
 
 
 

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

BOJ 2251번 물통  (0) 2020.01.24
BOJ 1525번 퍼즐  (0) 2020.01.24
BOJ 1963번 소수 경로  (0) 2020.01.23
BOJ 13913번 숨바꼭질4  (0) 2020.01.23
BOJ 13549번 숨바꼭질3  (0) 2020.01.22

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

+ Recent posts

티스토리툴바