[BOJ_16953] A->B (실버 1) - JAVA

---

🐾 알고리즘

• BFS(같이 안생겼지만 BFS)
• 다른 친구들의 풀이를 보면 역으로 생각해서 B-> A로 가는 풀이도 볼 수 있었다. 
• 자료형 잘 보기 (int 의 범위를 넘어가는지?)

---

🐾 생각 포인트

• cnt(연산횟수)를 어디서 계수 해주어야 되는지 고민이 많았다. 그러나 Pos(사용자 정의 클래스)를 만들어서 num과 cnt를 인자로 하여 queue에 반복적으로 삽입이 되도록 코드를 짰다.
• 종료조건을 짜서 flag를 선언해 주었다. 이를 통해 최종 값인 B에 도달했는지 안했는지 체크할 수 있었다.
• 처음엔 int로 선언하였으나, 연산을 거치면서 int의 범위를 넘어간다는 것을 알았다. num을 long으로 선언하면 스무스하게 패스할 수 있었다.

 

---

🐾 소스코드

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 Main_16953 {
	static class Pos {
		long num;
		int cnt;

		public Pos(long num, int cnt) {
			super();
			this.num = num;
			this.cnt = cnt;
		}

	}

	static int A;
	static int B;
	static boolean flag;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		A = Integer.parseInt(st.nextToken());
		B = Integer.parseInt(st.nextToken());

		bfs(A);
		if (flag == false) {
			System.out.println(-1);
		}
	}

	private static void bfs(int num) {
		Queue<Pos> queue = new LinkedList<>();
		queue.add(new Pos(num, 1));
		while (!queue.isEmpty()) {
			Pos t = queue.poll();
			
			// 종료조건
			if (t.num * 2 == B || t.num * 10 + 1 == B) {
				flag = true;
				System.out.println(t.cnt + 1);
				return;
			}
			// 반복(b에 도달할 때까지)
			if (t.num * 2 < B) {
				queue.add(new Pos(t.num * 2, t.cnt + 1));
			}

			if (t.num * 10 + 1 < B) {
				queue.add(new Pos(t.num * 10 + 1, t.cnt + 1));
			}

		}

	}
}

---

😵‍💫 공부해야 할 점

• 어떤 문제든 cnt가 발목을 잡을 때가 심심치않게 많다. 여기저기 다 cnt를 해보면서 코드를 동작시키는데, 이런 습관을 고쳐야할 필요가 있는 것 같다.
• 자료형을 꼼꼼히 보자.