Algorithm/백준
백준 [13913] 숨바꼭질 4
youngjae-kim
2024. 2. 21. 11:38
728x90
반응형
13913번: 숨바꼭질 4
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일
www.acmicpc.net
풀이
이전 방문 지점들을 저장하고 출력하는 부분의 구현이 떠오르지 않았다. 처음 시도한 방법은 뒤, 앞, 순간이동을 통해 갈 수 있는 케이스를 클래스로 이전 노드들을 저장해가면서 구현을 해보려 했는데 모든 경우들이 다 저장되는 문제가 있었고 정확하게 최단 거리만 저장할 수 없는 문제가 있었다.
그래서 다른 풀이를 참고 했음. 풀이의 핵심은 다음과 같다.
- 방문을 할 때마다 이전 노드의 위치를 담을 배열을 활용
- 스택에 배열의 k 번째 노드 부터 이전 위치를 찾아가면서 스택에 담고 스택을 출력
정답 코드
package com.baekjoon.p13913;
import java.util.*;
public class Main {
static int n, k;
static int[] arr = new int[100001];
static int[] before = new int[100001];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
StringBuilder sb = new StringBuilder();
n = sc.nextInt();
k = sc.nextInt();
bfs();
sb.append(arr[k] + "\n");
Stack<Integer> s = new Stack<>();
int i = k;
while (i != n) {
s.push(i);
i = before[i];
}
s.push(n);
while (!s.isEmpty()) {
sb.append(s.pop() + " ");
}
System.out.println(sb);
sc.close();
}
private static void bfs() {
Queue<Integer> q = new LinkedList<>();
q.add(n);
while (!q.isEmpty()) {
int now = q.poll();
if (now == k) {
return;
}
int back = now - 1;
int front = now + 1;
int jump = now * 2;
if (back >= 0 && arr[back] == 0) {
arr[back] = arr[now] + 1;
q.add(back);
before[back] = now;
}
if (front < 100001 && arr[front] == 0) {
arr[front] = arr[now] + 1;
q.add(front);
before[front] = now;
}
if (jump < 100001 && arr[jump] == 0) {
arr[jump] = arr[now] + 1;
q.add(jump);
before[jump] = now;
}
}
}
}
728x90
반응형