[백준(Baekjoon)][자바(java)] 13913 : 숨바꼭질 4 / 동적 계획법과 최단거리 역추적

 

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

13913번: 숨바꼭질 4

 

문제 풀이

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	static class Dot {
		int pos, time; // pos : position
		public Dot(int pos, int time) {
			this.pos = pos;
			this.time = time;
		}
	}

	public static void main(String[] args) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken()),
			k = Integer.parseInt(st.nextToken());
		br.close();

		final int max = 100001;  Dot dot;
		int answer = 0, i, pos, time, pos_next[], p, time_next;
		
		Queue<Dot> queue = new LinkedList<>();
		queue.add(new Dot(n, 0));

		boolean v[] = new boolean[max];
		v[n] = true;

		int dp[] = new int[max]; // 인덱스 : 현재 위치, 값 : 이전 위치

		// BFS
		loop:
		while (!queue.isEmpty()) {
			dot = queue.remove();
			pos = dot.pos;
			time = dot.time;
			pos_next = new int[]{pos * 2, pos + 1, pos - 1};
			time_next = time + 1;
			for (i = 0; i < 3; ++i) {
				p = pos_next[i];
				if (p < 0 || p >= max || v[p])
					continue;
				dp[p] = pos;
				if (p == k) {
					answer = time_next;
					break loop;
				}
				queue.add(new Dot(p, time_next));
				v[p] = true;
			}
		}

		StringBuilder sb = new StringBuilder();
		sb.append(k);
		int path = k; i = 0;
		while (i++ < answer)
			sb.insert(0, (path = dp[path]) + " ");
		sb.insert(0, answer + "\n");

		System.out.println(sb.toString());
	}
}

 

-  BFS로 N에서 K까지 탐색

-  dp 배열 생성 후 현재 위치를 인덱스로 하고 이전 위치를 값으로 저장

-  K(도착점)를 시작으로 dp를 역추적 해가며 값을 이어 붙임

 

---

[백준(Baekjoon)][자바(java)] 1697 : 숨바꼭질 / DFS와 BFS

https://hyunjiishailey.tistory.com/157

[백준(Baekjoon)][자바(java)] 1697 : 숨바꼭질 / DFS와 BFS