1697번: 숨바꼭질
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 ��
www.acmicpc.net
문제해석
- 수빈이가 동생을 잡으려고 하는데 2*X, X+1, X-1로 이동 가능함
- 최소의 이동으로 동생의 위치에 도달하는 방법 찾기 (=최적의 길)-> BFS
- 오직 BFS로만 풀리는 문제
SOL
- BFS로 구현
#include <iostream>
#include <queue>
using namespace std;
int n, m, ans;
queue<pair<int, int>> q;
bool vi[1000001];
void solve() {
q.push({ n, 0 });
vi[n] = 1;
while (!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
if (x == m) {
ans = y;
break;
}
for (int w = 0; w < 3; w++) {
if (w == 0 && vi[x - 1] == 0 && x - 1 >= 0) {
q.push({ x - 1, y + 1 });
vi[x - 1] = 1;
}
else if (w == 1 && vi[x + 1] == 0 && x + 1 < 100001) {
q.push({ x + 1, y + 1 });
vi[x + 1] = 1;
}
else if (w == 2 && vi[x * 2] == 0 && x * 2 < 100001) {
q.push({ x * 2, y + 1 });
vi[x * 2] = 1;
}
}
}
}
int main() {
cin >> n >> m;
solve();
cout << ans << endl;
return 0;
}
Java
import java.util.*;
import java.io.*;
class Location
{
int x;
int y;
Location(int x, int y)
{
this.x = x;
this.y = y;
}
}
public class Main
{
static boolean[] vi = new boolean[100001];
public static void bfs(int a, int b)
{
Arrays.fill(vi, false);
Queue<Location> q = new LinkedList<Location>();
q.add(new Location(a,0));
vi[a] = true;
while(!q.isEmpty())
{
Location temp = q.poll();
if(temp.x == b)
{
System.out.print(temp.y);
break;
}
int x = temp.x;
int y = temp.y;
x = temp.x-1;
y = temp.y+1;
if(x>=0 && vi[x] == false)
{
vi[x] = true;
q.add(new Location(x,y));
}
x = temp.x+1;
y = temp.y+1;
if(x<=100000 && vi[x] == false)
{
vi[x] = true;
q.add(new Location(x,y));
}
x = temp.x *2;
y = temp.y+1;
if(x<=100000 && vi[x] == false)
{
vi[x] = true;
q.add(new Location(x,y));
}
}
}
public static void main(String[] args) throws IOException
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str = br.readLine();
StringTokenizer st = new StringTokenizer(str);
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
bfs(a,b);
}
}'Algorithm' 카테고리의 다른 글
| [백준2667] 단지번호 붙히기 (C++, Java) (0) | 2020.09.03 |
|---|---|
| [백준 1987] 알파벳 (C++, Java) (0) | 2020.09.03 |
| [프로그래머스] 폰켓몬 C++, Java (0) | 2020.09.03 |
| [프로그래머스] 도둑질 (C++, Java) (0) | 2020.09.03 |
| [프로그래머스] 단어변환 (0) | 2020.07.20 |
