유형 : BFS
💡 아이디어
수빈이가 동생을 찾을 수 있는 가장 빠른 시간을 구하려면 BFS를 사용하면 된다.
하지만 이 문제는 어떻게 이동하는지 경로까지 출력해야 하기 때문에, 처음에는 Point 클래스에 route라는 String을 저장해서 추가하는 방식으로 풀었는데 => 6%에서 시간 초과
String에 +를 하게 되면 문자열이 수정되는게 아니라 새로 String 객체가 만들어짐을 알면서도 이렇게 풀이했다.
따라서 prev 배열에 현재 좌표 값을 다음 값 인덱스에 저장을 한다. 예를 들어, 현재 좌표가 x, 다음 좌표가 x - 1이라면 prev[x - 1] = x와 같이 저장하는 것이다.
첫번째 풀이에서는 BFS를 통해 최소 이동 횟수를 구한 뒤, 그만큼 DFS를 돌면서 역순으로 이동 경로를 출력했다. 하지만 굳이 재귀를 사용하기 보다는 반복문을 사용해서 스택에 저장한 뒤, 역순으로 출력하는 방식이 더 효율적임을 알고 수정하였다. 실제로 메모리 차원에서는 크게 차이나지 않지만 시간에서는 크게 차이가 남을 볼 수 있다.
풀이
첫번째 풀이 : BFS + DFS
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static class Point {
int coordinate;
int count;
Point (int coordinate, int count) {
this.coordinate = coordinate;
this.count = count;
}
}
static int N, K, answer;
static int[] prev;
static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
Queue<Point> queue = new ArrayDeque<>();
boolean[] visited = new boolean[100001];
prev = new int[100001];
queue.add(new Point(N, 0));
visited[N] = true;
while (!queue.isEmpty()) {
Point cur = queue.poll();
int x = cur.coordinate;
int c = cur.count;
if (x == K) {
answer = c;
break;
}
if (x - 1 >= 0 && !visited[x - 1]) {
queue.add(new Point(x - 1, c + 1));
visited[x - 1] = true;
prev[x - 1] = x;
}
if (x + 1 <= 100000 && !visited[x + 1]) {
queue.add(new Point(x + 1, c + 1));
visited[x + 1] = true;
prev[x + 1] = x;
}
if (x * 2 <= 100000 && !visited[x * 2]) {
queue.add(new Point(x * 2, c + 1));
visited[x * 2] = true;
prev[x * 2] = x;
}
}
sb.append(K);
dfs(K, 0);
}
public static void dfs(int start, int count) {
if (count == answer) {
System.out.println(answer + "\n" + sb);
return;
}
sb.insert(0, prev[start] + " ");
dfs(prev[start],count + 1);
}
}두번째 풀이 : BFS + 스택
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static class Point {
int coordinate;
int count;
Point (int coordinate, int count) {
this.coordinate = coordinate;
this.count = count;
}
}
static int N, K, answer;
static int[] prev;
static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
Queue<Point> queue = new ArrayDeque<>();
boolean[] visited = new boolean[100001];
prev = new int[100001];
queue.add(new Point(N, 0));
visited[N] = true;
while (!queue.isEmpty()) {
Point cur = queue.poll();
int x = cur.coordinate;
int c = cur.count;
if (x == K) {
answer = c;
break;
}
if (x - 1 >= 0 && !visited[x - 1]) {
queue.add(new Point(x - 1, c + 1));
visited[x - 1] = true;
prev[x - 1] = x;
}
if (x + 1 <= 100000 && !visited[x + 1]) {
queue.add(new Point(x + 1, c + 1));
visited[x + 1] = true;
prev[x + 1] = x;
}
if (x * 2 <= 100000 && !visited[x * 2]) {
queue.add(new Point(x * 2, c + 1));
visited[x * 2] = true;
prev[x * 2] = x;
}
}
Deque<Integer> stack = new ArrayDeque<>();
stack.add(K);
int p = K;
for (int i = 0; i < answer; i++) {
stack.add(prev[p]);
p = prev[p];
}
System.out.println(answer);
while (!stack.isEmpty()) {
System.out.print(stack.pollLast() + " ");
}
}
}두번째 풀이 리팩토링 : Point 클래스 대신 dist 배열 사용
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
Queue<Integer> queue = new ArrayDeque<>();
int[] dist = new int[100001];
int[] prev = new int[100001];
Arrays.fill(dist, -1);
queue.add(N);
dist[N] = 0;
while (!queue.isEmpty()) {
int cur = queue.poll();
if (cur == K) {
break;
}
if (cur - 1 >= 0 && dist[cur - 1] == -1) {
queue.add(cur - 1);
dist[cur - 1] = dist[cur] + 1;
prev[cur - 1] = cur;
}
if (cur + 1 <= 100000 && dist[cur + 1] == -1) {
queue.add(cur + 1);
dist[cur + 1] = dist[cur] + 1;
prev[cur + 1] = cur;
}
if (cur * 2 <= 100000 && dist[cur * 2] == -1) {
queue.add(cur * 2);
dist[cur * 2] = dist[cur] + 1;
prev[cur * 2] = cur;
}
}
int answer = dist[K];
Deque<Integer> stack = new ArrayDeque<>();
stack.add(K);
int p = K;
while (p != N) {
stack.add(prev[p]);
p = prev[p];
}
System.out.println(answer);
while (!stack.isEmpty()) {
System.out.print(stack.pollLast() + " ");
}
}
}
백엔드 개발자 연습생