[백준/Java] 1697 - 숨바꼭질

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

문제

---

풀이

배열을 기반으로 BFS 탐색을 진행한다

수빈의 위치가 2라고 가정하면 배열[2] 위치에 1로 초기화하고

현재 위치에서 x - 1(1), x + 1(3), 2 * x(4)의 인덱스 위치의 값을 전 값에서 +1 해주면 된다

 

다음은 1, 3, 4를 차례로 큐에 넣고 하나씩 빼면서 반복해주면 된다

주의할 점은 걸리는 시간의 최솟값을 찾아야 하기 때문에 한 번 방문한 곳은 값 갱신을 하지 않는다

동생 위치가 5라면 인덱스 5의 값이 채워지면 그 값 - 1을 리턴해주면 된다. (처음 위치의 값을 1로 잡았기 때문에)

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

	static int N, K;
	static int[] visited = new int[100001]; // 방문 여부

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

		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());   // 수빈 위치
		K = Integer.parseInt(st.nextToken());   // 동생 위치

		System.out.println(bfs(N));

		br.close();
	}

	static int bfs(int node) {
		Queue<Integer> queue = new LinkedList<>();

		visited[node] = 1;  // 방문 처리
		queue.offer(node);

		// 큐가 빌 때까지
		while (!queue.isEmpty()) {
			int nextIndex = queue.poll();

			// 동생 위치에 도착했으면
			if (nextIndex == K) {
				// 배열 값 - 1 리턴
				return visited[nextIndex] - 1;
			}
			// x - 1이 범위 안이고, 방문하지 않았다면
			if (nextIndex - 1 >= 0 && visited[nextIndex - 1] == 0) {
				// x - 1 위치 값 = x 위치 값 + 1
				visited[nextIndex - 1] = visited[nextIndex] + 1;
				// x - 1 위치를 큐에 넣는다
				queue.offer(nextIndex - 1);
			}
			// x + 1이 범위 안이고, 방문하지 않았다면
			if (nextIndex + 1 <= 100000 && visited[nextIndex + 1] == 0) {
				// x + 1 위치 값 = x 위치 값 + 1
				visited[nextIndex + 1] = visited[nextIndex] + 1;
				// x + 1 위치를 큐에 넣는다
				queue.offer(nextIndex + 1);
			}
			// 2 * x가 범위 안이고, 방문하지 않았다면
			if (2 * nextIndex <= 100000 && visited[2 * nextIndex] == 0) {
				// 2 * x 위치 값 = x 위치 값 + 1
				visited[2 * nextIndex] = visited[nextIndex] + 1;
				// 2 * x 위치를 큐에 넣는다
				queue.offer(2 * nextIndex);
			}
		}

		return -1;
	}

}

결과