[BOJ] 1697. 숨바꼭질

문제

BOJ 1697. 숨바꼭질

풀이

최소 시간을 묻는 문제이므로 그래프 중 bfs를 사용했다.
이미 방문한 곳이면 재방문 할 필요는 없기 때문에 visited로 방문여부를 체크해주었고 Point클래스로 위치와 시간을 동시에 관리했다. Queue는 선입선출이니까 먼저 도착한 애가 가장 짧은 시간 내에 도착한 애라고 생가하여 동생을 발견하면 바로 return해주었다.

JAVA코드

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 백준1697_숨바꼭질 {
	
	static int ans;
	static class Point {
		int idx;
		int time;

		public Point(int idx, int time) {
			super();
			this.idx = idx;
			this.time = time;
		}
	}

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

		StringTokenizer st = new StringTokenizer(br.readLine());

		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());

		System.out.println(ans);
	}

	public static void bfs(int N, int K) {
		Queue<Point> queue = new LinkedList<>();
		boolean[] visited = new boolean[100001];

		queue.add(new Point(N, 0));// 시작 지점 queue에 add
		while (!queue.isEmpty()) {

			// queue.poll()
			Point current = queue.poll();

			// 방문했어? 그럼 그냥 넘긴다.
			if (visited[current.idx])
				continue;

			// 현재 위치==동생? 그럼 return!
			if (current.idx == K) {
				ans = current.time;
				return;
			}

			// 방문 안했으면 방문처리하고
			visited[current.idx] = true;

			// 범위체크하고 내 양옆/순간이동 위치 queue에 넣기!
			if (current.idx - 1 >= 0) {
				queue.add(new Point(current.idx - 1, current.time + 1));
			}

			if (current.idx + 1 < 100001) {
				queue.add(new Point(current.idx + 1, current.time + 1));
			}
			if (current.idx * 2 < 100001 && current.idx * 2 >= 0) {
				queue.add(new Point(current.idx * 2, current.time + 1));

			}
		}

	}

}