Baekjoon Online Judge

algorithm practice

-問題を逐次解く

24.DFSとBFS

8.かくれんぼ

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

public class Main {
	static int N, K;
	static int result;
	static int[] check = new int[100001];
	static Queue<Integer> queue = new LinkedList<>();
    
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));        
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());

		if (N == K) {
			bw.write("0\n");
		} else {
			bfs(N);
			bw.write(result + "\n");
		}
        
		bw.flush();
		bw.close();
		br.close();
	}

	public static void bfs(int num) {       
		queue.add(num);
		check[num] = 1;

		while (!queue.isEmpty()) {
			int temp = queue.poll();

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

				if (i == 0) {
					next = temp + 1;
				} else if (i == 1) {
					next = temp - 1;
				} else {
					next = temp * 2;
				}

				if (next == K) {
					result = check[temp];
					return;
				}
				if (next >= 0 && next < check.length && check[next] == 0) {
					queue.add(next);
					check[next] = check[temp] + 1;
				}
			}
		}        
	}
}

from collections import deque
import sys
N, K = map(int, sys.stdin.readline().split())
MAX = 10**5
dist = [0]*(MAX + 1)

# bfs 경로 탐색
def bfs():
    queue = deque()
    queue.append(N)
    while queue:
        x = queue.popleft()
    
        if x == K:
            print(dist[x])
            break
        for nx in (x-1, x+1, x*2):    # nx = 4, 6, 10
            if 0 <= nx <= MAX and not dist[nx]:
                dist[nx] = dist[x] + 1
                queue.append(nx)

bfs()