[백준] 13913번 : 숨바꼭질 java

문제 설명

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

첫째 줄에 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.
둘째 줄에 어떻게 이동해야 하는지 공백으로 구분해 출력한다.

예제

풀이

 골드4치고는 쉬운문제  같지만..
풀이가 개판이다..
나중에 다른방식으로도 풀어봐야 겠다.

기본 bfs 탐색에 
Node Class를 만들어서
매번 새로운 list를 생성하는 방식이다.

그래서 무려 메모리 300MB 사용 ㅋ.ㅋ
그치만 다른 방법이 생각이 안났다.

코테 스터디원의 풀이를 보니까 stack을 사용해서 푸시는 분도 있던데
한번 고민해 봐야겠다....

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Bj13913 {

    private static int K;
    private static int[] visited = new int[100_001];
    private static List<Integer> list;

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

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

		// N 과 K 가 같으면 탐색할 필요가없음.
        if (N == K) {
            System.out.println(0);
            System.out.println(K);
            return;
        }
		
        // N > K 보다 크면 시간복잡도가 제곱단위로 올라가서 예외적으로 넣어주는게 좋다.
        if (N > K) {
            System.out.println(N - K);

            for (int i = N; i >= K; i--) {
                sb.append(i).append(" ");
            }
            System.out.println(sb);
            return;
        }

        bfs(N);

        System.out.println(visited[K]-1);
        for (Integer integer : list) {
            sb.append(integer).append(" ");
        }
        System.out.println(sb);

    }

    private static void bfs(int N) {
        Queue<Node> q = new LinkedList<>();
        q.add(new Node(N, List.of(N)));

        visited[N] = 1;

        while (!q.isEmpty()) {
            Node node = q.poll();

            int point = node.point;
            List<Integer> nodeList = node.list;

            int up = point + 1;
            int down = point - 1;
            int jump = point * 2;

            if (jump <= 100000 && visited[jump] == 0) {
            	// nodeList의 데이터를 바탕으로 새로운 list를 생성
                List<Integer> jumpList = new ArrayList<>(nodeList);
                jumpList.add(jump);

                q.add(new Node(jump, jumpList));
                visited[jump] = visited[point] + 1;
				
                
                // 만약 동생을 찾았으면 클래수 변수를 현재 list로 대입해준다.
                if (jump == K) {
                    list = jumpList;
                    break;
                }
            }

            if (up <= 100000 && visited[up] == 0) {
                List<Integer> upList = new ArrayList<>(nodeList);
                upList.add(up);

                q.add(new Node(up, upList));
                visited[up] = visited[point] + 1;

                if (up == K) {
                    list = upList;
                    break;
                }
            }


            if (down >= 0 && visited[down] == 0) {
                List<Integer> downList = new ArrayList<>(nodeList);
                downList.add(down);

                q.add(new Node(down, downList));
                visited[down] = visited[point] + 1;

                if (down == K) {
                    list = downList;
                    break;
                }
            }
        }
    }

    static class Node {
        int point;
        List<Integer> list;
        public Node(int nowPoint, List<Integer> list) {
            this.point = nowPoint;
            this.list = list;
        }

    }

}