https://www.acmicpc.net/problem/18112
18112번: 이진수 게임
첫 번째 줄에 길이 L의 ‘시작 이진수’가 주어진다. 두 번째 줄에 길이 K의 ‘목표 이진수’가 주어진다. (1 ≤ L, K ≤ 10)
www.acmicpc.net
- 맨 앞 숫자를 제외한 한 자리 숫자를 보수로 바꾸기
- 현재 수에 1 더하기
- 현재 수에 1 빼기 (현재 수가 자연수일 때만 해당)
위 과정을 반복하여 시작 이진수 s가 목표 이진수 e가 되는 최소 동작 횟수를 출력하는 문제로 오랜만에 bfs입니다.
입력은 10자리 이진수로 주어지며, 저는 이 수를 10진수로 변환하여 비트마스킹을 이용하였습니다.
이 풀이의 로직은
먼저, 이진수를 10진수로 변환하고, s를 시작으로 bfs 탐색합니다.
그 다음은 x가 0인 경우를 제외하고 한 비트씩 변경된 값을 queue에 넣습니다.
이 과정에서 bit가 x / 2보다 커진다면 마지막 비트이므로 break를 걸어줍니다.
e가 10자리 이진수이므로 1024보다 작은 수입니다.
따라서 x + 1이 1024보다 작은 경우에만 queue에 넣어주면 됩니다.
그리고 e는 음수가 아니므로 x가 자연수일 경우에만 x - 1을 queue에 넣어줍니다.
위의 과정을 반복하여 e에 도착하면 t를 리턴하여 출력합니다.
|
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
|
#include <iostream>
#include <queue>
#include <string>
#define MAX 10
using namespace std;
string str1, str2;
bool visit[1 << MAX];
int s, e;
int bfs() {
queue<int> q;
q.push(s);
visit[s] = 1;
for (int t = 0; !q.empty(); t++) {
int qsize = q.size();
while (qsize--) {
int x = q.front();
q.pop();
if (x == e) {
return t;
}
int bit = 1;
while (1) {
if (!x) break;
if (x & bit) {
if (bit > x / 2) break;
}
int next = x ^ bit;
if (!visit[next]) {
q.push(next);
visit[next] = true;
}
bit <<= 1;
}
if (x + 1 < 1024 && !visit[x + 1]) {
q.push(x + 1);
visit[x + 1] = true;
}
if (x && !visit[x - 1]) {
q.push(x - 1);
visit[x - 1] = true;
}
}
}
return 0;
}
void func() {
cout << bfs() << '\n';
}
void init() {
int len1 = str1.size();
int mul = 1;
for (int i = len1 - 1; i >= 0; i--) {
if (str1[i] == '1') s += mul;
mul <<= 1;
}
int len2 = str2.size();
mul = 1;
for (int i = len2 - 1; i >= 0; i--) {
if (str2[i] == '1') e += mul;
mul <<= 1;
}
}
void input() {
cin >> str1 >> str2;
init();
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
input();
func();
return 0;
}
|
cs |
'algorithm > bfs' 카테고리의 다른 글
| boj 16985 Maaaaaaaaaze (0) | 2022.12.16 |
|---|---|
| boj 14466 소가 길을 건너간 이유 6 (0) | 2022.10.13 |
| boj 16946 벽 부수고 이동하기 4 (0) | 2022.05.22 |
| boj 5547 일루미네이션 (0) | 2022.05.15 |
| boj 16932 모양 만들기 (0) | 2022.05.14 |