[백준][Java] 숨바꼭질 3

문제링크

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

13549번: 숨바꼭질 3

 

# 문제 풀이

수빈이가 할 수 있는 이동은 크게 두가지가 있습니다. 걷기와 순간이동입니다. 둘은 각각 아래와 같습니다.

걷기 -> 1초, x+1 or x-1

순간이동 -> 0초, 2x

수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구해야합니다.

 

저는 탐색 조건을 아래와 같이 정했습니다.

1. 이동했을 때, 수빈이의 위치가 정해진 범위를 벗어나지 않는지 검사

2. 첫 방문이라면 몇초에 방문했는지 입력하고, 큐에 넣기

3. 이전에 왔다면, 그전의 방문보다 이르게 도착하는 경로인 경우, 저장하고 큐에 넣기

제가 정한 탐색 조건에 따라 수빈이가 할 수 있는 이동의 종류를 bfs로 구현하였습니다.

 

# 문제 코드

public class Main {
	static int n, k;
	static int[] visited = new int[100001];

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

		n = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());

		bfs();

		System.out.println(visited[k]);
	}

	public static void bfs() {
		Queue<Node> q = new LinkedList<Node>();
		q.add(new Node(n, 0));
		Arrays.fill(visited, -1);
		visited[n] = 0;

		while (!q.isEmpty()) {
			Node node = q.poll();

			if (node.x - 1 >= 0 && (visited[node.x - 1] > node.count + 1 || visited[node.x - 1] == -1)) {
				visited[node.x - 1] = node.count + 1;
				q.add(new Node(node.x - 1, node.count + 1));
			}
			if (node.x + 1 <= 100000 && (visited[node.x + 1] > node.count + 1 || visited[node.x + 1] == -1)) {
				visited[node.x + 1] = node.count + 1;
				q.add(new Node(node.x + 1, node.count + 1));
			}
			if (2 * node.x <= 100000 && (visited[2 * node.x] > node.count || visited[2 * node.x] == -1)) {
				visited[2 * node.x] = node.count;
				q.add(new Node(2 * node.x, node.count));
			}
		}
	}

	public static class Node {
		int x, count;

		public Node(int x, int count) {
			super();
			this.x = x;
			this.count = count;
		}
	}
}