알고리즘: 백준 1697번 숨바꼭질 (feat. c++)

백준 1697번 링크입니다. 

1697번: 숨바꼭질

 

bfs를 이용하면 문제가 생각보다 쉽게 풀린다. 

 

최대 가능 인풋이 100000이기 때문에 시간복잡도가 최대 n^2 까지 가능하다고 생각하였다.

 

최단거리 문제이기도 해서 bfs를 선택하였다.

 

#include<iostream>
#include<queue>
using namespace std;
int visit[100001];

bool check(int x) { //check 함수가 중요한듯!
	if (x < 0 | x > 100001) return false;
	if (visit[x] == 1) return false;

	return true;



}

int bfs(int N, int K) {
	
	queue<int> qx, qc;
	qx.push(N);  // K 값을 찾기위한 여정의 준비
	qc.push(0);  // 거리를 카운트한다. 
	int count = 0;
    
	while (!qx.empty()) { 
		
		int cx = qx.front(); qx.pop();
		int cc = qc.front(); qc.pop();
		
		if (visit[cx] == 1)continue;  //이미 방문한 곳이면 넘어가자
		
		visit[cx] = 1;  //방문하지 않았으면 방문처리 

		if (cx == K)  // 원하는 값을 찾았으면 count에 넣어준다.  
		{
			count = cc;  
			break;
		}
		
        if (check(cx * 2)) {  
			qx.push(cx * 2);
			qc.push(cc + 1);
		}
		
        if (check(cx + 1)) {
			qx.push(cx + 1);
			qc.push(cc + 1);
		}
		
        if (check(cx - 1)) {
			qx.push(cx - 1);
			qc.push(cc + 1);
		}
		
		
	}

	return count;
}

int main() {

	int N, K;
	scanf("%d%d", &N, &K);
	printf("%d\n", bfs(N, K));
	
	return 0;
}

 

bfs에 익숙하지 않아서 "이 문제를 푸는데 bfs를 사용해서 풀어야 한다" 까지 오래걸렸다.

 

최단거리 문제가 나오면 bfs를 떠올리자.