69 삐약 : 백준 13913| 숨바꼭질4 [바킹독 문제 풀이|BFS|JAVA]

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

 

 

우엑 꽝 기각

...중략...
        q.offer(new Location(N, new StringBuilder().append(N)));
...중략...
        while(!q.isEmpty()){
            Location l = q.poll();
...중략...
			ways=l.way.toString();
                }
            }
            if(l.x+1<=100000 && load[l.x+1]==0){
                load[l.x+1]=load[l.x]+1;
                q.offer(new Location(l.x+1,new StringBuilder(l.way).append(" ").append(l.x + 1)));
            }
...중략...
    }

    static class Location{
        int x; // 위치
        StringBuilder way;

        public Location(int x, StringBuilder way){
            this.x = x;
            this.way =way;
        }
    }

}

 

초반에는 위치 값과 진행 순서를 문자열로 저장하는 클래스를 선언하여 문제를 풀이하려 했다.

그러나 이전에도 겪었듯이 문자열 클래스를 사용하는 것은 메모리상에도 접근하는 시간 상에도 큰 부담을 줄 수 있다는 것을 알고 있기에

변동성을 생각하여 StringBuilder로 변경하였지만 내가 볼땐 새로 Stringbuilder를 선언하는 것 또한 부담이 없지 않은 것 같다고 판단하였다.

 

 

 

위와 같은 이유로 이전에 배열 문제를 풀 때 많이 적용했었던 이전 경로를 저장하는 방식으로 풀이에 접근하였다.

 

package BKD_0x9_BFS;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;

public class BOJ_13913 {
    static int[] load = new int[100001];
    static int[] parent = new int[100001];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();

        int N = sc.nextInt();
        int K = sc.nextInt();
        parent[N]=-1;

        getDst(N,K);

        Stack<Integer> st = new Stack<>();
        int way = K;

        while(way!=-1){
            st.push(way);
            way = parent[way];
        }
        while(!st.isEmpty()){
            sb.append(st.pop()+" ");
        }


        System.out.println(load[K]-1);
        System.out.println(sb.toString());



    }
    static void getDst(int N, int K){
        Queue<Integer> q = new LinkedList<>();
        q.offer(N);
        load[N]=1; // 시간 체크

        while(!q.isEmpty()){
            int current = q.poll();

            if(current == K){
                break;
            }
            if(current+1<=100000 && load[current+1]==0){
                load[current+1]=load[current]+1;
                parent[current+1] = current;
                q.offer(current+1);
            }
            if(current-1>=0 && load[current-1]==0){
                load[current-1]=load[current]+1;
                parent[current-1] = current;
                q.offer(current-1);
            }
            if(current*2<=100000 && load[current*2]==0){
                load[current*2]=load[current]+1;
                parent[current*2] = current;
                q.offer(current*2);
            }


        }
    }
}

 

 

경로 추출에 필요한 방법을 생각하는데에 시간을 쪼오오오오로올오롱로오오롤오꼼 더 썼던 문제였다.