Karice의 여행 & 코딩 블로그

문제 설명

풀이

이번에는 다른 방식으로 BFS를 풀었다.

시간을 계속 들고다니고 간단한 BFS처럼 풀어주면 끝이다.

코드

import java.util.*;
import java.io.*;

class Main {
    static int N, K;
    static int minTime = Integer.MAX_VALUE;
    static boolean[] visit = new boolean[100001];

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        if (N >= K) {
            System.out.println((N-K));
            return;
        }
        else{
            bfs();
            System.out.println(minTime);
        }
    }

    public static void bfs() {
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[] {N, 0});

        while(!q.isEmpty()) {
            int[] node = q.poll();
            visit[node[0]] = true;
            if(node[0] == K) minTime = Math.min(minTime, node[1]);

            if(node[0] * 2 <= 100000 && visit[node[0] * 2] == false) q.offer(new int[] {node[0] * 2, node[1]});
            if(node[0] + 1 <= 100000 && visit[node[0] + 1] == false) q.offer(new int[] {node[0] + 1, node[1] + 1});
            if(node[0] - 1 >= 0 && visit[node[0] - 1] == false) q.offer(new int[] {node[0] - 1, node[1] + 1});
        }
    }

}

https://www.acmicpc.net/problem/13549

문제 설명

풀이

당연히 최소거리니까 DP가 아니라면 BFS문제이다.

일반적으로 최소거리를 찾으면 끝내는게 아니라, 최소거리가 나올때 마다 카운트를 추가해야한다

다소 어려운 방법으로 풀었지만, minTime 보다 time[now]가 크면 이미 조건 불만족이니 더 안간다

그리고 이렇게 계속해서 조건부적으로 시간을 체크해주면 가장 빠르게 할 수있다

코드

import java.util.*;
import java.io.*;

class Main {
    static int N, K;
    static int[] time = new int[100001];
    static int minTime = 987654321;
    static int count = 0;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        if (N >= K) {
            System.out.println((N-K) + "\n1");
            return;
        }

        bfs();

        System.out.println(minTime + "\n" + count);
    }

    static void bfs() {
        Queue<Integer> q = new LinkedList<Integer>();

        q.add(N);
        time[N] = 1;

        while (!q.isEmpty()) {
            int now = q.poll();

            // now 방문 시간이 최소 시간보다 크면 뒤는 더 볼 필요 없음
            if (minTime < time[now]) return;

            for (int i=0; i<3; i++) {
                int next;

                if (i == 0)         next = now + 1;
                else if (i == 1)    next = now - 1;
                else                next = now * 2;

                if (next < 0 || next > 100000) continue;

                if (next == K) {
                    minTime = time[now];
                    count++;
                }

                // 첫 방문이거나 (time[next] == 0)
                // 이미 방문한 곳이어도 같은 시간에 방문했다면 (time[next] == time[now] + 1)
                // 경우의 수에 추가될 수 있기 때문에 Queue 에 한번 더 넣어줌
                if (time[next] == 0 || time[next] == time[now] + 1) {
                    q.add(next);
                    time[next] = time[now] + 1;
                }
            }
        }
    }
}

https://www.acmicpc.net/problem/12851

문제 설명

풀이

바이러스를 퍼트리는건 똑같이  BFS로 퍼트리면 된다.

바이러스중에서 어떤 것을 활성화 시키면 가장 빨리 될지를 찾아야 되니, Backtracking으로 모든 경우의 수를 돌아볼 수 있게 해주면 끝!

중요코드 (백트래킹)

백트래킹이 자꾸 헷갈리는데 start와 count(종료조건)을 꼭 해두고 불필요한 반복은 안하게 만들자

    // 백트래킹으로 M 개의 바이러스를 선택하는 Combination 구현
    static void selectVirus(int start, int selectCount) {
        if (selectCount == M) {
            spreadVirus(originEmptySpace);
            return;
        }

        for (int i = start; i < viruses.size(); i++) {
            active[selectCount] = viruses.get(i);
            selectVirus(i + 1, selectCount + 1);
        }
    }

코드

import java.util.*;
import java.io.*;

class Main {
    static class Virus {
        int x, y, time;

        Virus(int x, int y, int time) {
            this.x = x;
            this.y = y;
            this.time = time;
        }
    }

    static int N, M;
    static int[][] arr;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static List<Virus> viruses = new ArrayList<>();
    static Virus[] active;
    static int resultMinTime = Integer.MAX_VALUE;
    static int originEmptySpace = 0;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        // input
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        
        arr = new int[N][N];
        active = new Virus[M];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());

            for (int j = 0; j < N; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());

                if (arr[i][j] == 0) {
                    originEmptySpace++;
                } else if (arr[i][j] == 2) {
                    viruses.add(new Virus(i, j, 0));
                }
            }
        }

        // solution
        if (originEmptySpace == 0) {
            System.out.println(0);
        } else {
            selectVirus(0, 0);
            System.out.println(resultMinTime == Integer.MAX_VALUE ? -1 : resultMinTime);
        }
    }

    // 백트래킹으로 M 개의 바이러스를 선택하는 Combination 구현
    static void selectVirus(int start, int selectCount) {
        if (selectCount == M) {
            spreadVirus(originEmptySpace);
            return;
        }

        for (int i = start; i < viruses.size(); i++) {
            active[selectCount] = viruses.get(i);
            selectVirus(i + 1, selectCount + 1);
        }
    }

    // BFS 로 바이러스를 퍼트린다
    static void spreadVirus(int emptySpace) {
        Queue<Virus> q = new LinkedList<>();
        boolean[][] infected = new boolean[N][N];

        for (int i = 0; i < M; i++) {
            Virus virus = active[i];
            infected[virus.x][virus.y] = true;
            q.add(virus);
        }

        while (!q.isEmpty()) {
            Virus virus = q.poll();

            for (int i = 0; i < 4; i++) {
                int nx = virus.x + dx[i];
                int ny = virus.y + dy[i];

                if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
                if (infected[nx][ny] || arr[nx][ny] == 1) continue;

                if (arr[nx][ny] == 0) {
                    emptySpace--;
                }

                if (emptySpace == 0) {
                    resultMinTime = Math.min(resultMinTime, virus.time + 1);
                    return;
                }

                infected[nx][ny] = true;
                q.add(new Virus(nx, ny, virus.time + 1));
            }
        }
    }
}

문제 설명

풀이

역시나 결국 같은 유형의 병사들의 숫자를 구해서 제곱을 해서 각각 따로 더해주면 된다 간단한 BFS문제

코드

import java.util.*;
import java.io.*;

class Main {
    static int N,M;
    static int c =0;
    static Character[][] map;
    static int[][] visit;
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};
    static Queue<int[]> que = new LinkedList<>();

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        M = sc.nextInt();
        N = sc.nextInt();

        map = new Character[N][M];
        visit = new int[N][M];
        int me = 0;
        int you = 0;
        sc.nextLine();
        for (int i = 0; i < N; i++) {
            String str = sc.nextLine();
            for (int j = 0; j < M; j++) {
                map[i][j] = str.charAt(j);
            }
        }

        for(int i=0; i<N; i++){
            for(int j=0; j<M; j++){
                if (visit[i][j] != 1){
                    c=1;
                    que.add(new int[] {i,j});
                    visit[i][j] = 1;
                    bfs();
                    if(map[i][j]=='W')
                        me += c*c;
                    else
                        you += c*c;
                }
            }
        }

        System.out.println(me + " " + you);
    }

    static void bfs() {
        // bfs 시작
        while(!que.isEmpty()) {
            int[] out = que.poll();
            int x = out[0];
            int y = out[1];

            for(int i=0; i<4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];

                if(0 > nx || nx >= N || 0 > ny || ny >= M || visit[nx][ny] == 1) {
                    continue;
                }
                if (map[nx][ny] != map[x][y])
                    continue;
                c++;
                visit[nx][ny] = 1;
                que.add(new int[] {nx, ny});
            }
        }
    }
}

https://www.acmicpc.net/problem/1303

문제 설명

풀이

BFS로 해서 섬마을 구간 나누기 처럼 가장 큰 덩어리를 찾으면 된다. BFS를 돌리면서 쓰레기가 근처에 있으면 que에 넣고 카운트를 추가해주면서 계속 진행시키면 끝!

코드

import java.util.*;
import java.io.*;

class Main {
    static int N,M,T;
    static int[][] map,visit;
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        T = Integer.parseInt(st.nextToken());

        map = new int[N+1][M+1];
        visit = new int[N+1][M+1];
        int count = 0;

        while(T-- >0){
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            map[x-1][y-1] = 1;
        }
        for(int i=0; i<N; i++){
            for(int j=0; j<M; j++){
//                System.out.print(map[i][j] +" ");
                if (map[i][j] == 1 && visit[i][j] == 0){
                    int result = bfs(i,j);
                    if (count < result){
                        count = result;
                    }
                }
            }
//            System.out.println();
        }
        System.out.println(count);
    }

    static int bfs(int a, int b) {
        Queue<int[]> que = new LinkedList<>();
        int cnt = 1;
        que.add(new int[] {a,b});
        visit[a][b] = 1;

        // bfs 시작
        while(!que.isEmpty()) {
            int[] out = que.poll();
            int x = out[0];
            int y = out[1];

            for(int i=0; i<4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];

                if(0 > nx || nx >= N || 0 > ny || ny >= M || visit[nx][ny] == 1) {
                    continue;
                }
                if(map[nx][ny] == 1) {
                    visit[nx][ny] = 1;
                    cnt = cnt+1;
                    que.add(new int[] {nx, ny});
                }
            }
        }
        return cnt;
    }
}

https://www.acmicpc.net/problem/1743

문제 설명

풀이

간단한 BFS문제, 익은 토마토를 기준으로 계속 Queue에 넣어주고 안익은 토마토를 지워주면 된다. BFS의 원리만 알면 정말 쉽게 풀 수 있는 문제

코드

import java.util.*;
import java.io.*;

class Main {
    static int N;
    static int M;
    static int[][] box;
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};

    static class Dot {
        int x;
        int y;
        int day;

        public Dot(int x, int y, int day) {
            this.x = x;
            this.y = y;
            this.day = day;
        }
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        box = new int[M][N];

        for(int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());

            for(int j=0; j<N; j++) {
                box[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        bfs();
    }

    static void bfs() {
        Queue<Dot> q = new LinkedList<Dot>();
        int day = 0;

        // 토마토가 있는 좌표 찾아서 Queue에 넣기
        for(int i=0; i<M; i++) {
            for(int j=0; j<N; j++) {
                if(box[i][j] == 1)
                    q.offer(new Dot(i, j, 0));
            }
        }

        // bfs 시작
        while(!q.isEmpty()) {
            Dot dot = q.poll();
            day = dot.day;

            for(int i=0; i<4; i++) {
                int nx = dot.x + dx[i];
                int ny = dot.y + dy[i];

                if(0 <= nx && nx < M && 0 <= ny && ny < N) {
                    if(box[nx][ny] == 0) {
                        box[nx][ny] = 1;
                        q.add(new Dot(nx, ny, day+1));
                    }
                }
            }
        }

        // 토마토가 다 익었는지 확인
        if(checkTomato())
            System.out.println(day);
        else
            System.out.println(-1);
    }

    // box 배열에 0이 남아있다면 false, 아니면 true
    static boolean checkTomato() {
        for(int i=0; i<M; i++) {
            for(int j=0; j<N; j++) {
                if(box[i][j] == 0)
                    return false;
            }
        }

        return true;
    }
}

https://www.acmicpc.net/problem/7576

문제 설명

풀이

기본적인 BFS로 푸는 좌표 이동 문제. 그냥 나이트의 이동경로만 다르지 크게 다른 문제와 다를 것은 없음. 매우매우 쉬운 문제!

코드

import java.io.*;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int T,N,x1,y1,x2,y2;
    static int[][] map;
    static int[][] visit;
    static int[] dx = {1,2,2,1,-1,-2,-2,-1};
    static int[] dy = {2,1,-1,-2,-2,-1,1,2};

    public static void main(String[] args) throws IOException {
        // 1. 값 입력받기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        T = Integer.parseInt(br.readLine());
        while(T-- >0){
//            System.out.println(T+"번쨰");
            N = Integer.parseInt(br.readLine());
            map = new int[N+1][N+1];
            visit = new int[N+1][N+1];
            StringTokenizer st = new StringTokenizer(br.readLine());
            x1 = Integer.parseInt(st.nextToken());
            y1 = Integer.parseInt(st.nextToken());

            st = new StringTokenizer(br.readLine());
            x2 = Integer.parseInt(st.nextToken());
            y2 = Integer.parseInt(st.nextToken());

            if(x1 == x2 && y1 == y2){
                System.out.println(0);
            }
            else{
                bfs(x1,y1,x2,y2,N);
            }
        }


    }

    private static int bfs(int x1, int y1, int x2, int y2, int N) {
        Queue<int[]> que = new LinkedList<>();
        int c = 0;
        que.add(new int[] {x1,y1,c});
        visit[x1][y1] = 1;

        while (!que.isEmpty()) {
            int[] out = que.poll();
            int xx = out[0];
            int yy = out[1];
            int cnt = out[2];

            for(int i=0; i<8; i++){
                int dr = xx + dx[i];
                int dc = yy + dy[i];

                if( dr < 0 || dc < 0 || dr > N-1 || dc > N-1 || visit[dr][dc] == 1){
                    continue;
                }

                if(dr == x2 && dc == y2){
                    System.out.println(cnt+1);
                    return 0;
                }
                visit[dr][dc] = 1;
                que.add(new int[] {dr,dc,cnt+1});
            }
        }
        return 0;
    }
}

https://www.acmicpc.net/problem/7562

문제 설명

풀이

기본적으로 BFS로 풀어야된다는 것을 알고 있어야 한다.

그리고 생각보다 안복잡하고 간단한데, 안에 있는 공기는 신경안 써도 되는게, 밖에 있는 공기를 기준으로 BFS를 돌리면 된다는 것이다.

밖에 있는 빈칸을 기준으로 BFS를 돌리고, 경계면에 있는 치즈를 바로 0으로 바꿔주면서, 계속 Roop 시키면 끝!

배운것 : 복잡하게 생각하지 말고, 천천히 생각해보자

코드

import java.io.*;
import java.util.*;

public class Main {
	public static int N, M, cheese, cnt, time;
	public static int[][] map;
	public static boolean[][] v;
	public static int[] dx = { -1, 1, 0, 0 };
	public static int[] dy = { 0, 0, -1, 1 };

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		map = new int[N][M];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				if (map[i][j] == 1)
					cheese++;
			}
		}
		while (cheese != 0) {
			time++;
			cnt = cheese;
			meltingCheese();
		}
		System.out.println(time);
		System.out.println(cnt);
	}

	public static void meltingCheese() {
		Queue<int[]> que = new LinkedList<int[]>();
		que.offer(new int[] { 0, 0 });
		v = new boolean[N][M];
		v[0][0] = true;
		while (!que.isEmpty()) {
			int[] cur = que.poll();
			for (int i = 0; i < 4; i++) {
				int nx = cur[0] + dx[i];
				int ny = cur[1] + dy[i];
				if (nx < 0 || nx >= N || ny < 0 || ny >= M || v[nx][ny]) continue;
				if (map[nx][ny] == 1) {
					cheese--;
					map[nx][ny] = 0;
				} else if (map[nx][ny] == 0) {
					que.offer(new int[] { nx, ny });
				}
				v[nx][ny] = true;
			}
		}
	}
}

문제 설명

풀이

BFS, DFS로 모두 풀 수 있는 문제이다. 일단 그래프 문제인 것은 바로 알 수 있고, 특별히 어느 것을 골라도 상관없을 듯하다.

풀이는, 일단 한 점을 잡고 쭉 DFS, BFS를 돌린다. 그러면 붙어있는 것들은 모두 visit = true가 될 것이고, 다음 탐색을 하면서 또 함수를 돌리고, 이렇게 반복하면 쉽게 풀 수 있다.

코드

BFS

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    private static int dx[] = {0,0,1,-1};
    private static int dy[] = {1,-1,0,0};
    private static int[] aparts = new int[25*25];
    private static int n;
    private static int apartNum = 0; //아파트 단지 번호의 수
    private static boolean[][] visited = new boolean[25][25]; //방문여부
    private static int[][] map = new int[25][25]; //지도

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();

        map = new int[n][n];
        visited = new boolean[n][n];

        //전체 사각형 입력 받기
        for(int i=0; i<n; i++){
            String input = sc.next();
            for(int j=0; j<n; j++){
                map[i][j] = input.charAt(j)-'0';
            }
        }

        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(map[i][j] == 1 && !visited[i][j]){
                    apartNum++;
                    bfs(i,j);
                }
            }
        }

        Arrays.sort(aparts);
        System.out.println(apartNum);

        for(int i=0; i<aparts.length; i++){
            if(aparts[i] == 0){
            }else{
                System.out.println(aparts[i]);
            }
        }

    }

    private static void bfs(int x, int y) {
        //2차원 LinkedList를 가진 큐 선언
        Queue<int[]> que = new LinkedList<>();
        que.add(new int[]{x,y});
        visited[x][y] = true;
        aparts[apartNum]++;

        while(!que.isEmpty()){

            //x, y 값을 받아오기 위한 방법
            int curX = que.peek()[0];
            int curY = que.peek()[1];
            que.poll();

            for(int i=0; i<4; i++){
                int nx = curX + dx[i];
                int ny = curY + dy[i];

                if(nx >= 0 && ny >= 0 && nx < n && ny < n){
                    if(map[nx][ny] == 1 && !visited[nx][ny]){
                        que.add(new int[]{nx,ny});
                        visited[nx][ny] = true;
                        aparts[apartNum]++;
                    }
                }
            }
        }
    }
}

DFS

import java.io.*;
import java.util.Arrays;

public class Main {
    private static int num;
    private static int[][] map;
    private static int n;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        map = new int[n+2][n+2];
        for (int i = 1; i <= n; ++i) {
            char[] t = br.readLine().toCharArray();
            for (int j = 1; j <= n; ++j) {
                map[i][j] = t[j-1]-'0';
            }
        }
        br.close();
        num = 2;

        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (map[i][j] == 1) {
                    dfs(i, j);
                    ++num;
                }
            }
        }
        int[] nums = new int[num];
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (map[i][j] !=  0) {
                    ++nums[map[i][j]-2];
                }
            }
        }
        Arrays.sort(nums);
        num = 0;
        for (int i = 0; i < nums.length; ++i) {
            if (nums[i] != 0) {
                nums[num++] = nums[i];
            }
        }
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(String.valueOf(num));
        bw.newLine();
        for (int i = 0; i < num; ++i) {
            bw.write(String.valueOf(nums[i]));
            bw.newLine();
        }
        bw.close();
    }

    private static void dfs(int i, int j) {
        map[i][j] = num;
        if (map[i+1][j] == 1)
            dfs(i+1, j);
        if (map[i-1][j] == 1)
            dfs(i-1, j);
        if (map[i][j+1] == 1)
            dfs(i, j+1);
        if (map[i][j-1] == 1)
            dfs(i, j-1);
    }
}

https://www.acmicpc.net/problem/2667

문제 설명

풀이

기본적인 BFS 문제, 이런 경우 DFS로 할경우 오히려 늦어지는 경우가 많았음. BFS로 모든 경우의 수를 찾아가면 금방 찾아감!

코드

import java.io.*;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int N,M;
    static int[] visit;

    public static void main(String[] args) throws IOException {
        // 1. 값 입력받기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        visit = new int[100001];
        if (N == M) {
            System.out.println(0);
        } else {
            System.out.println(bfs());
        }
    }

    private static long bfs() {
        Queue<Integer> que = new LinkedList<>();
        que.add(N);
        visit[N] = 1;

        while (!que.isEmpty()) {
            int out = que.poll();

            if (out == M) {
                return visit[out]-1;
            }
            if ( out * 2 <= 100000 && visit[out * 2] == 0){
                visit[out*2] = visit[out] + 1;
                que.add(out * 2);
            }
            if ( out + 1 <= 100000 && visit[out + 1] == 0 ){
                visit[out+1] = visit[out] + 1;
                que.add(out + 1);
            }
            if ( out - 1 >= 0 && visit[out -1] == 0 ){
                visit[out-1] = visit[out] + 1;
                que.add(out - 1);
            }
        }

        return -1;
    }
}

왜 틀린건지 모르는 내 해쉬를 사용한 코드...

import java.io.*;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static long N,M;
    static HashMap<Long, Long> map = new HashMap<>();

    public static void main(String[] args) throws IOException {
        // 1. 값 입력받기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Long.parseLong(st.nextToken());
        M = Long.parseLong(st.nextToken());
        if (N == M) {
            System.out.println(0);
        } else {
            System.out.println(bfs());
        }
    }

    private static long bfs() {
        Queue<long[]> que = new LinkedList<>();
        que.add(new long[] {N,0});

        while (!que.isEmpty()) {
            long[] out = que.poll();
            System.out.println(out[0]+"count : "+ out[1]);

            if (out[0] == M) return out[1];
            if ( out[0] * 2 <= M && !map.containsKey(out[0]*2)){
                map.put(out[0] * 2, out[1]+1);
                que.add(new long[] {out[0] * 2,out[1]+1});
            }
            if ( out[0] + 1 <= M && !map.containsKey(out[0] + 1) ){
                map.put(out[0] + 1, out[1]+1);
                que.add(new long[] {out[0] + 1,out[1]+1});
            }
            if ( out[0] - 1 > 0 && !map.containsKey(out[0] - 1) ){
                map.put(out[0] - 1, out[1]+1);
                que.add(new long[] {out[0] - 1,out[1]+1});
            }
        }

        return -1;
    }
}

https://www.acmicpc.net/problem/1697