Baekjoon Online Judge

algorithm practice

- 단계별 문제풀기

27. 동적 계획법과 최단거리 역추적

지금까지는 최솟값, 최댓값, 최단거리만 찾았습니다. 이번에는 실제 최적해와 최단경로를 찾아 봅시다.

Java / Python

6. 숨바꼭질 4

13913번

BFS 최단경로를 출력하는 문제

이번 문제는 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하는 문제입니다.
수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어지고, 첫째 줄에 수빈이가 동생을 찾는 가장 빠른 시간을 출력하고, 둘째 줄에 어떻게 이동해야 하는지 공백으로 구분해 출력하면 됩니다.

• Java

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

public class Main {
	static int N, K;
	static int[] move = new int[100001];
	static int[] time = new int[100001];

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();

		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());

		bfs();

		Stack<Integer> stack = new Stack<>();
		stack.push(K);
		int idx = K;

		while (idx != N) {
			stack.push(move[idx]);
			idx = move[idx];
		}

		sb.append(time[K] - 1 + "\n");

		while (!stack.isEmpty()) {
			sb.append(stack.pop() + " ");
		}

		bw.write(sb.toString());

		bw.flush();
		br.close();
		bw.close();
	}

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

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

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

			if (now == K)
				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 (time[next] == 0) {
					queue.add(next);
					time[next] = time[now] + 1;
					move[next] = now;
				}
			}
		}
	}
}

• Python

import sys
input = sys.stdin.readline
from collections import deque

def bfs():
    que = deque()
    que.append(N)
    while que:
        x = que.popleft()
        if x == K:
            print(visit[x])
            result = []
            while x != N: 
                result.append(x) 
                x = move[x] 
            result.append(N) 
            result.reverse() # 역순으로 저장되어 있으므로 순서를 바꿈 
            print(' '.join(map(str, result))) 
            return
        for i in (x+1, x-1, 2*x):
            if 0<=i<=100000 and visit[i] == 0:
                que.append(i)
                visit[i] = visit[x] + 1
                move[i] = x
                
N, K = map(int, input().split())
visit = [0]*100001
move = [0]*100001
bfs()x