BOJ_1697_숨바꼭질

이 글은 개발을 공부하는 '학생'의 글입니다. 틀린 내용이 있을 수 있음을 미리 공지합니다. 혹시 오류를 발견하신 분이 계신 경우, 댓글을 남겨주시면 정말 감사드리겠습니다:)

BFS 문제를 앞으로도 쭉 풀 것이지만, 다른 단원으로 넘어가기 전 마지막 문제를 풀어보겠습니다. 숨바꼭질 문제인데요. 이 문제의 경우, 2차원 grid로 풀었던 기존의 문제와는 다른 양상이기 때문에 BFS로 풀어야함을 쉽게 인지하기 쉽지 않았던 것 같습니다. 하지만 BFS의 기본 개념, 너비로 뻗어나감을 좀 더 다른 측면에서 볼 수 있는 문제이므로 한 번 풀어보겠습니다.

문제 출처 : https://www.acmicpc.net/problem/1697

접근방법

• 수빈이와 동생이 N, K점에 각각 있다고 한다.
  -> 1차원 배열
• 수빈이가 현재 위치가 X일 때 1초 후, X-1, X+1, 2*X위치로 이동할 수 있다.
• 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하자.
  -> 수빈이가 t초에 특정 점에 있다고 하자. 해당 점에서 X-1, X+1, 2*X위치로 이동 했을 때는 t + 1초 일 것이다.
  -> 모든 점에 대해서 시간을 계산한 후, 혹은 동생의 점에 있에 도착했을 때, 그 값을 출력하면 정답일 것이다.
• 한 가지 주의해야할 점이 있다. 수빈이와 동생의 현재 위치는 한정되어 있지만, 이동 중에는 한정되어 있지 않다.
  -> 따라서 수빈이는 10만이라는 위치에서 x2를 해서 20만 위치에 있을 수도 있다.
  -> 물론 이 문제에서는 x2를 하고 -1을 여러번 한 것이, -1을하고 x2를 한 것 보다 손해이다.
  -> 8만을 간다고 했을 때, 5만 -> x2 -> -20000, 5만 -> -10000 -> x2 두 개를 비교해보면 오른쪽이 훨씬 더 빠르다는 것을 알 수 있다.
  -> 9만을 간다고 해도, 5만 -> x2 -> -10000, 5만 -> -5000 -> x2 이 와 같이 결국에는 -를 하고 x를 진행하는 것이 빠르다.
  -> 따라서, 10만을 배열로 잡아도 충분하다.
• 마찬가지로 음수의 위치를 다녀오는 것도 굳이?가 될 수 있다.
• 시간복잡도를 봐보자. N이 10만까지므로 O(N)은 10만. BFS로 충분하다.

시간복잡도 : O(N)

#include<iostream>
#include<queue>
using namespace std;

int n, k;
int arr[100002];	// 배열 변수를 바로 visited 처리하는 데에 활용할 것이다.

int main() {
	cin >> n >> k;
	fill(arr, arr + 100002, -1);	// 방문 안한점 -1처리
	queue<int> q;
	q.push(n);
	arr[n] = 0;
	while (!q.empty()) {
		int curr = q.front(); q.pop();
		if (curr == k) break;
		int np = curr + 1;
		int np2 = curr - 1;
		int np3 = curr * 2;
		// 해당 점이 범위 안이고, 방문하지 않았던 점이라면
		// &&을 통해서 앞의 값이 거짓이라면 뒤의 값을 판단하지 않도록해서
		// array 범위가 넘어가는 일을 없도록 방지한다.
		if (np >= 0 && np < 100002 && arr[np] == -1) {
			arr[np] = arr[curr] + 1;
			q.push(np);
		}
		if (np2 >= 0 && np2 < 100002 && arr[np2] == -1) {
			arr[np2] = arr[curr] + 1;
			q.push(np2);
		}
		if (np3 >= 0 && np3 < 100002 && arr[np3] == -1) {
			arr[np3] = arr[curr] + 1;
			q.push(np3);
		}
	}
	cout << arr[k];
	return 0;
}

추가로 공부한 부분

• BFS에서 np, np2, np3를 판단할 때, else if를 썼어서 오류가 났다.
  -> 각각 판단해야 하는 부분이라 if를 쓰는 것이 맞았다.