[자바] 백준 13913번: 숨바꼭질 4

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

13913번: 숨바꼭질 4

---

처음 시도했던 풀이는

 

바텀업 방식으로, dp[0]부터 dp[k]까지 최소 이동횟수를 저장하는 식으로 했다.

최소경로 출력에서 잘못된 건지 이동횟수가 잘못계산된 건지 답이 자꾸 틀렸다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

public class P13913 {

	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());
		StringBuffer[] path = new StringBuffer[k+1];
		
		if(n>=k) {
			System.out.println(n-k);
			for(int i=n;i>=k;i--) {
				System.out.print(i+" ");
			}
			return;
		}
		path[n]=new StringBuffer(n+" ");
		int[] dp= new int[k+1];
		for(int i=n-1;i>=0;i--) {
			dp[i]=n-i;
			path[i]=new StringBuffer(path[i+1].toString()+i+" ");
		}
		for(int i=n+1;i<=k;i++) {
			
			dp[i]=dp[i-1]+1;
			if(i%2==0) {
				if(dp[i]>dp[i/2]+1)
					dp[i]=dp[i/2]+1;
					path[i]=new StringBuffer(path[i/2].toString()+i+" ");
					continue;
			}
			path[i]=new StringBuffer(path[i-1].toString()+i+" ");
		}
		
		System.out.println(dp[k]);
		System.out.println(path[k].toString());
//		
//		int current=k;
//		Stack<Integer> stack = new Stack<>();
//		stack.add(current);
//		int next=k-1;
//		
//		while(current!=n&&current>0) {
//			if(current<n) {
//				next=current+1;
//				
//			}
//			else {
//				next=current-1;
//				if(current%2==0) {
//					if(dp[next]>dp[current/2])
//					{
//						next=current/2;
//						current=next;
//						stack.add(current);
//						continue;
//					}
//				}
//			}
//			
//			current=next;
//			
//			stack.add(current);
//			
//		}
//		System.out.println(dp[k]);
//		while(!stack.isEmpty()) {
//			System.out.print(stack.pop()+" ");
//		}
	}

}

경로를 어떻게 출력해야 할 지 엄청나게 고민했다

처음에는 도착지부터 역으로 내려가다가,

경로가 잘못될 수도 있겠다는 생각으로

매 위치마다 경로를 StringBuffer에 저장했는데

메모리를 너무 많이 사용해서 이 방법도 쓸 수 없었다.

 

---

그래서 bfs방식으로 다시 풀었다.

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

public class P13913 {

	static int[] visited= new int [100001];
	static int[] parent=new int[100001];
	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());
		
		bfs(n,k);
		
		System.out.println(visited[k]-1);
		
		int now=k;
		StringBuffer sb= new StringBuffer();
		while(now!=n) {
			sb.insert(0, now+" ");
			now=parent[now];
		}
		sb.insert(0, now+" ");
		
		System.out.println(sb);

	}
	static void bfs(int start,int end) {
		visited[start]=1;
		
		Queue<Integer> q= new LinkedList<Integer>();
		q.add(start);
		
		while(!q.isEmpty()) {
			int now=q.poll();
			
			if(now+1<=100000 && visited[now+1]<=0) {
				q.add(now+1);
				visited[now+1]=visited[now]+1;
				parent[now+1]=now;
			}
			if(now-1>=0 && visited[now-1]<=0) {
				q.add(now-1);
				visited[now-1]=visited[now]+1;
				parent[now-1]=now;
			}
			if(now*2<=100000 && visited[now*2]<=0) {
				q.add(now*2);
				visited[now*2]=visited[now]+1;
				parent[now*2]=now;
			}
			if(now==end) {
				return;
			}
		}
	}
}

 

visited[]에는 이동횟수가 저장되는데

visited[start]=0으로 해놓고 시작하는 실수를 저질렀다.

(그러면 visited[start]는 아직 방문하지 않은것으로 간주되어 나중에 visited[start]값이 변한다)

 

그래서 1로 시작하도록 하고 출력시에 1 감소시켜야 했다.