Baekjoon - 1697

문제

Solved.ac Class3

1차시도

public class Main {
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String[] split = br.readLine().split(" ");
		int n = Integer.parseInt(split[0]);
		int k = Integer.parseInt(split[1]);

		if (n == k) {
			System.out.println(0);
		} else {
			System.out.println(bfs(n, k));
		}

	}

	private static int bfs(int start, int target) {
		int[] visitList = new int[100000 + 1];
		Queue<Integer> queue = new LinkedList<>();
		queue.add(start);
		visitList[start] = 1;

		while (!queue.isEmpty()) {
			int value = queue.remove();

			for (int i = 0; i < 3; i++) {
				int visit;
				if (i == 0) {
					visit = value + 1;
				} else if (i == 1) {
					visit = value - 1;
				} else {
					visit = value * 2;
				}

				if (visit == target) {
					return visitList[value];
				}

				if (visit >= 0 && visitList[visit] == 0 && visit < 100000 + 1) {
					queue.add(visit);
					visitList[visit] = visitList[value] + 1;
				}
			}
		}
		return -1;
	}
}

런타임 에러

2차시도

위 if문을 보면

if (visit >= 0 && visitList[visit] == 0 && visit < 100000 + 1)

visitList를 먼저 방문하고 범위를 체크한다. 이렇게 되면 범위를 넘어서 검증을 할 수도 있다. 이러면 안되기 때문에 순서 바꾸기

if (visit >= 0 && visit < target + 2 && visitList[visit] == 0) {
	queue.add(visit);
	visitList[visit] = visitList[value] + 1;
}

실패

3차시도

위 코드를 보면

if (visit >= 0 && visit < target + 2 && visitList[visit] == 0)

visit < target+2 로 해두었는데 x2 를 하고 4~5번 빼는게 더 효율적일 수도 있다. 그렇기 때문에 최대 길이로 정해주었다.

if (visit >= 0 && visit < visitList.length && visitList[visit] == 0) {
	queue.add(visit);
	visitList[visit] = visitList[value] + 1;
}

성공