[백준]숨바꼭질4(13913번)

https://www.acmicpc.net/problem/13913
//1 문제 분석

너비 우선 탐색을 통해 주어진 목적지까지의 최소 시간과 그 경로를 구하는 문제이다.

//2 문제 해결

방문 체크 겸 시간경과를 계산할 배열과 목적지가 어떤 위치에서 왔는지 나타낼 배열 두개를 사용하였다. 너비 우선 탐색을 통해 걸리는 시간을 계산하였고 목적지부터 시작 위치까지의 역 경로를 ArrayList에 저장후 역순으로 출력하였다.

//3 작성 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class HideAndSeek4_13913 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stz = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();
		int[] visited = new int[100001];
		int[] before = new int[100001];
		int N = Integer.parseInt(stz.nextToken());
		int K = Integer.parseInt(stz.nextToken());
		bfs(visited,before,N,K);
		sb.append(visited[K]-1).append("\n");
		ArrayList<Integer> arr = new ArrayList<>();
		int temp = K;
		while (true) {
			arr.add(temp);
			if (temp==N) break;
			temp = before[temp];
		}
		for (int i = arr.size()-1; i>=0; i--) {
			sb.append(arr.get(i)).append(" ");
		}
		System.out.println(sb);
		
	
	}
	
	static void bfs(int[] visited, int[] before, int N, int K) {
		ArrayDeque<Integer> q = new ArrayDeque<>();
		q.add(N);
		visited[N]=1;						//시작점을 1로 시작
 		while(!q.isEmpty()) {
			int temp = q.poll();
			int[] npoint = {temp-1,temp+1,temp*2};
			for (int i = 0 ; i<3 ; i++) {
				if (npoint[i]<100001 && npoint[i]>=0) {
					if(visited[npoint[i]]==0) {
						visited[npoint[i]]=visited[temp]+1;
						q.add(npoint[i]);
						before[npoint[i]]=temp;
						if(npoint[i]==K) return;
					}
				}
			}
		}
	} 
}

//4 시행착오

처음은 bfs안의 while문 안쪽에서 -1이동 +1이동 x2이동 세가지 코드를 따로 작성하였는데, 코드가 반복되는 느낌이 강해서 npoint라는 배열을 만들고 반복문으로 중복 코드를 묶었다.

//5 개선 가능성

크기가 큰 배열 두개를 사용하였는데 시간 계산을 다른 방식으로 하면 배열을 하나만 사용할 수 있을 것이다. 또한 경로를 출력할 때 List말고 Stack 자료 구조를 사용하면 실행 시간을 단축할 수 있을 것이다.