[백준 1697] 숨바꼭질 C++, Java

www.acmicpc.net/problem/1697

1697번: 숨바꼭질

 

문제해석

 

• 수빈이가 동생을 잡으려고 하는데 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); 
    	
        
        
    }
}