백준 1697번 : 숨바꼭질

문제 접근

---

최단 경로 찾기의 느낌이 들어서 BFS 로 풀었다. 나는 N 에서 K 로 접근하는 게 아니라 K 에서 N 으로 접근하는 방법으로 풀었다. N 에서 K 로 접근하면 텔레포트(2배) 하는 경우를 항상 고려해야돼서 큐에 들어가는 값이 많아지지만, K 에서 N 으로 접근하면 K 가 짝수일 때만 텔레포트를 고려하면 돼서 비교적 적은 양으로 처리할 수 있었다. 사소한 차이지만 효율이 좋아지니 나쁘지 않은 것 같다.

 

제출 했을 때 자꾸 런타임 에러나서 찾아보니 주로 아래와 같은 이유로 에러가 발생한다고 한다.

 

1) 배열 인덱스 범위를 벗어나는 경우

2) 잘못된 공간에 접근하는 경우

3) 0으로 나누는 경우

 

확인해보니 44행 ~ 51행 if 문에서 && 연산자로 조건을 확인할 때 연산 결과 인덱스가 visited 의 인덱스 범위를 초과하는지부터 확인한 게 아니라, 연산 결과 인덱스에 해당하는 visited 값이 false 인지 확인을 해서 visited[-1] 이나 visited[100001] 에 접근이 됐던 것이다. 따라서 조건을 확인하는 순서를 바꿔서 해결했다.

 

 

문제 코드

---

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int main(void)
{
	int N,K;
	
	cin>>N>>K;
	
	vector<bool> visited(100000,false);
	vector<int> prc;
	vector<int> rsv;
	int ans = 0;
	bool flag = false;
	
	if(K<N)
	{
		ans = N-K+1;
		flag = true;
	}
	
	queue<vector<int>> q;
	q.push(vector<int>(1,K));
	
	while(!flag)
	{
		prc = q.front();
		rsv.clear();
		q.pop();
		
		for(int i=0; i<prc.size(); ++i)
		{
			visited[prc[i]]=true;
			
			if(prc[i]==N)
			{
				flag = true;
				break;
			}
			
			if(prc[i]-1>-1 && !visited[prc[i]-1])
				rsv.push_back(prc[i]-1);
			
			if(prc[i]%2==0 && !visited[prc[i]/2])
				rsv.push_back(prc[i]/2);
			
			if(prc[i]+1<100001 && !visited[prc[i]+1])
				rsv.push_back(prc[i]+1);
		}
		
		q.push(rsv);
		++ans;
	}
	
	cout<<ans-1<<'\n';
	
	return 0;
}