Baekjoon Online Judge

algorithm practice

- 단계별 문제풀기

24. DFS와 BFS

그래프를 순회하는 알고리즘을 배워 봅시다.

Java / Python

8. 숨바꼭질

1697번

또 다른 BFS 최단거리 연습문제

이번 문제는 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하는 문제입니다.
BFS 탐색을 이용했습니다.

• Java

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;
				}
			}
		}        
	}
}

• Python

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()