[알고리즘][X] 숨바꼭질 2

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

12851번: 숨바꼭질 2

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;

public class Main {
	static int N;
	static int K;
	static int[] map;
	static boolean[] visited;
	static int count;
	static int number;
	static boolean flag;
	static StringBuilder sb = new StringBuilder();
	static class Node {
		int start;
		int depth;
		public Node(int start, int depth) {
			super();
			this.start = start;
			this.depth = depth;
		}
		
	}
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());

		visited = new boolean[100001];
		
		if (N == K) {
			sb.append(0).append("\n").append(1);
			System.out.println(sb);
			return;
		}
		count = 0;
		number = 0;
		flag = false;
		bfs(new Node(N, 0));
		sb.append(count).append("\n").append(number);
		System.out.println(sb);
	}

	private static void bfs(Node start) {
		Deque<Node> deque = new ArrayDeque<>();
		deque.add(start);
		visited[start.start] = true;
		while (!deque.isEmpty()) {
			Node curs = deque.poll();
			int cur = curs.start;
			int depth = curs.depth;
			visited[cur] = true;
			if (cur == K) {
				if (!flag) {
					flag = true;
					count = depth;
					number++;
				} else {
					if (depth == count) {
						number++;
					} else if (depth > count) {
						return;
					}
				}
				visited[cur] = false;
			}
			if (0 <= cur - 1 && cur - 1 <= 100000 && visited[cur - 1] != true) {
				deque.add(new Node(cur - 1, depth+1));
			} 
			if (0 <= cur + 1 && cur + 1 <= 100000 && visited[cur + 1] != true) {
				deque.add(new Node(cur + 1, depth+1));	
			} 
			if (0 <= cur * 2 && cur * 2 <= 100000 && visited[cur * 2] != true) {
				deque.add(new Node(cur * 2, depth+1));	
			}
		}
		
	}
}

나의 풀이

- 같은 위치일 때 예외처리를 했는데 출력을 안해줘서 틀렸다.

- 또한 sb를 bfs 안에 넣어서 틀렸다.

- 또한 이 문제는 1이 2가 될 때 1 + 1, 1 * 2가 될 수 있기 때문에 방문 처리는 나중에 해주어야 한다.