[BOJ] 1697 숨바꼭질

Time Lapse :NONE

1697.cpp

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
#include <iostream>
#include <memory.h>
#include <queue>
#include <map>
using namespace std;
int N,M;
map<int,int> m;
void BFS()
{
m.insert(make_pair(N,0));
queue<int> q;
q.push(N);
while(!q.empty())
{
if(m.find(M)!=m.end())
break;

int now = q.front();
int t = m.find(now)->second;
q.pop();
int tel = now*2;
int bef = now-1;
int aft = now+1;

if(m.find(tel)==m.end()&&tel<=100000&&tel>=0){
q.push(tel);
m.insert(make_pair(tel,t+1));
}
if(m.find(bef)==m.end()&&bef<=100000&&bef>=0){
q.push(bef);
m.insert(make_pair(bef,t+1));
}
if(m.find(aft)==m.end()&&aft<=100000&&aft>=0){
q.push(aft);
m.insert(make_pair(aft,t+1));
}
}
}

int main(void) {
cin >> N >> M;
BFS();
cout<<m.find(M)->second<<endl;
}

1697.java

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
import java.io.*;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
static Reader r = new Reader();
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
static boolean[] v = new boolean[100001];
public static void main(String[] args) throws IOException {
int val = r.nextInt(), k = r.nextInt(), ans = 0;
boolean f = val != k;
if(val > k) ans = val - k;
else {
Queue<Integer> q = new LinkedList<>();
q.add(val);
v[val] = true;
while(f) {
++ans;
int size = q.size();
for(int i = 0; i < size; ++i) {
val = q.remove();
if(val + 1 == k || val == k + 1 || (val<<1) == k) {
f = false;
break;
}
if(val >= 1 && !v[val-1]) {
q.add(val - 1);
v[val-1] = true;
}
if(val <= 99999 && !v[val+1]) {
q.add(val + 1);
v[val+1] = true;
}
if(val <= 50000 && !v[val<<1]) {
q.add(val<<1);
v[val<<1] = true;
}
}
}
}
bw.write(ans+"");
bw.flush();
}

static class Reader {
final private int BUFFER_SIZE = 1 << 16;
private DataInputStream din;
private byte[] buffer;
private int bufferPointer, bytesRead;

public Reader() {
din = new DataInputStream(System.in);
buffer = new byte[BUFFER_SIZE];
bufferPointer = bytesRead = 0;
}

public int nextInt() throws IOException {
int ret = 0, flag = 1;
byte c = read();
if(c == '-') {
flag = -1;
c = read();
}
do {
ret = (ret<<3) + (ret<<1) + (c & 0b1111);
} while ((c = read()) >= '0' && c <= '9');

return ret * flag;
}
public String readLine() throws IOException {
byte[] buf = new byte[64]; // line length
int cnt = 0, c;
while ((c = read()) != -1)
{
if (c == '\n')
break;
buf[cnt++] = (byte) c;
}
return new String(buf, 0, cnt);
}


private void fillBuffer() throws IOException {
bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
if (bytesRead == -1)
buffer[0] = -1;
}

private byte read() throws IOException {
if (bufferPointer == bytesRead)
fillBuffer();
return buffer[bufferPointer++];
}
}
}
Author: Song Hayoung
Link: https://songhayoung.github.io/2020/07/30/PS/BOJ/1697/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.