[백준] 1697번 숨바꼭질

문제링크

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

 

해설

seconds 배열 요소가 갱신됐으면 새로운 값으로 갱신되면 안 된다. 새로 갱신되는 값은 기존 값보다 무조건 클 것이기 때문이다. 우리는 최소 값을 구해야 하니까 방문한 요소는 건너뛰어 값을 보호하고 비효율도 예방한다. 그전에는 이런 최소 값을 구할 때 queue를  pair로 선언해 위치값과 거리 값을 같이 관리하는는 걸 선호했지만 이번에는 (x, y) 형태의 좌표에 관한 문제가 아니라 값을 갱신해나가면서 최소 값을 찾는 것이기 때문에 별도의 visited 배열을 두지 않고 하나의 정수형 배열에서 방문/미방문을 구분할 수 있다.

 

전체 코드

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

int N, K;
const int MAX_SIZE = 200000;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	cin >> N >> K;

	vector<int> seconds(MAX_SIZE + 1, -1);
	queue<int> q;

	seconds[N] = 0;
	q.push(N);

	int answer = 0;
	while (q.empty() == false)
	{
		int current = q.front();
		q.pop();

		if (current == K)
		{
			answer = seconds[K];
			break;
		}
		
        // 임시 initializer_list 객체를 만들어 연속 읽기 전용 메모리에서 직접 참조
        // 오버헤드 신경 안 써도 된다
		for (int next : {current - 1, current + 1, current * 2})
		{
			if (next < 0 || next > MAX_SIZE + 1 || seconds[next] != -1) continue;

			seconds[next] = seconds[current] + 1;
			q.push(next);
		}
	}

	cout << answer << endl;
}