[BOJ 1697] 숨바꼭질 (S1)

📍 문제 

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

 

📍 문제 풀이

수빈이가 이동할 수 있는 방법 3가지

1. 현재위치 (`cur`) + 1
2. 현재위치 (`cur`) - 1
3. 현재위치 (`cur`) * 2

`visited` 배열을 따로 둬서 위치별 방문 여부를 확인할 수 있지만

`dist` 배열을 전체 `-1`로 초기화하면서 방문 여부를 확인하였다. 

값이 `-1`라면 아직 방문하지 않은 위치이고 값이 `0`이상이라면 방문한 위치이다.

 

현재 위치를 `Queue`에 넣어주며 `dist`에는 현재 위치까지의 최소 시간을 입력한다.

이후 수빈이가 이동할 수 있는 3가지 위치(`next`)의 방문 가능 여부를 확인한다.

`next`가 범위 안에 존재하고, 방문하지 않았다면 방문 가능하다고 판단해 해당 값을 `Queue`에 넣어준다.

if (next >= 0 && next < dist.length && dist[next] == -1) {
	que.add(next);
	dist[next] = dist[cur] + 1;
}

 

📍 전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class boj_1697 {
	static int n, k;
	static int[] dist = new int[2000002];

	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());

		// visited 배열 없이 방문 여부를 확인하기 위해 사용
		// -1이면 아직 방문하지 않은 위치
		Arrays.fill(dist, -1);


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

	static void bfs(int pos) {
		Queue<Integer> que = new LinkedList<>();
		que.add(pos);
		dist[pos] = 0;

		while (!que.isEmpty()) {
			int cur = que.poll();
			int next;

			if (cur == k) {
				System.out.println(dist[cur]);
				return;
			}

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

				if (next >= 0 && next < dist.length && dist[next] == -1) {
					que.add(next);
					dist[next] = dist[cur] + 1;
				}
			}

		}
	}
}