[BaekJoon] 13913 숨바꼭질 4 (Java)

🔗 문제 링크

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

📝 문제 설명

현재 위치에서 3가지 이동 방법을 통해 이동을 하며 동생을 찾는 문제로 BFS를 사용하면 쉽게 해결할 수 있다.

이동 방법
1. x+1
2. x-1
3. x*2

BFS를 사용해 쉽게 해결할 줄 알았으나 문제의 메모리 제한이 적어 코드를 조금씩 변경해보며 많은 제출 끝에 통과할 수 있었다....

코드를 작성할 때 연산을 하나라도 줄일 수 있으면 줄이는 코딩 습관을 기르도록 하자!!

👨🏻‍💻 작성한 코드

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

public class Main {
	
	static boolean[] visited = new boolean[100001];
	static int[] parent = new int[100001];

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int subin = Integer.parseInt(st.nextToken());
		int sister = Integer.parseInt(st.nextToken());
		
		visited[subin] = true;
		bfs(subin, sister);
		
		Stack<Integer> stack = new Stack<>();
		stack.add(sister);
		int past = sister;
		
		while (past != subin) {
			past = parent[past];
			stack.add(past);
		}
		
		bw.write((stack.size()-1) + "\n");
		while(!stack.isEmpty()) {
			bw.write(stack.pop() + " ");
		}
		bw.flush();
		bw.close();
		br.close();
		
	}
	
	static void bfs(int subin, int sister) {	
		Queue<Integer> queue = new LinkedList<>();
		queue.add(subin);
		
		int next;
		int current;
		
		while(!queue.isEmpty()) {
			current = queue.poll();
			
			if (current == sister) break;
			
			for (int i=0; i<3; i++) {
				if (i == 0) next = current + 1;
				else if (i == 1) next = current - 1;
				else next = current * 2;
				
				if (0 > next || next > 100000) continue;
				
				if (!visited[next]) {
					queue.add(next);
					visited[next] = true;
					parent[next] = current;
				}
			}
		}
	}

}